Boar and hooves

Limits: 5 sec., 256 MiB

This statement was translated automatically from Ukrainian.

The playful boar KABAN was walking in the park and unexpectedly met other boars. Oink after oink and now the boars are already playing. KABAN suggested playing the following game (better he had walked in the park instead of such games):

KABAN is given the numbers \(n\), \(k\), and \(q\).

Then KABAN is asked \(q\) questions, in each question two numbers are given: \(g\) and \(s\).

He needs to count the number of integers \(x\) from \(0\) to \(n\) inclusive such that \(\sum_{p=0}^{\infty} \lfloor \frac{x}{k^p} \rfloor = g (mod \: s)\).

All of us are sometimes a little bit KABAN, but you are KABAN right now, so calculate everything like KABAN and output the answer to each question.

Input

The first line contains three integers \(n\), \(k\), and \(q\).

The next \(q\) lines each contain two integers: \(g\) and \(s\).

Output

Output \(q\) lines — the answers to the questions in the order they were asked.

Constraints

\(1 \le n \le 10^9\),

\(2 \le k \le 50\),

\(1 \le q \le 1000\),

\(1 \le s \le 10^5\),

\(0 \le g < s\),

\(s\) is a prime number.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 4 2 3 3 5 0 5 1 5	2 0 2 1