using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (n, m, p, q) = (c[0], c[1], c[2], c[3]); var ans = new int[q]; for (var u = 0; u < q; ++u) { c = NList; ans[u] = Country(m, c[0], c[1], p); } WriteLine(string.Join("\n", ans)); } static int Country(int m, int x, int f, int p) { var revx = Exp(x, p - 2, p); var ex = (int)(f * revx % p); if (ex > m) return 0; return (m - ex) / p + (ex > 0 ? 1 : 0); } static int GCD(int a, int b) { if (a < b) return GCD(b, a); if (a % b == 0) return b; return GCD(b, a % b); } static long Exp(long n, long k, int mod) { if (k == 0) return 1; if (k == 1) return n % mod; var half = Exp(n, k / 2, mod); var result = (half * half) % mod; return ((k % 2) == 0) ? result : ((result * n) % mod); } }