Кабанець і копитка

Limits: 5 sec., 256 MiB

Грайливий кабанець KABAN гуляв по парку і неочікувано зустрів інших кабанців. Хрюк за хрюк і ось, кабанці вже граються. KABAN запропонував зіграти в наступну гру (краще б по парку гуляв з такими іграми):

KABANу кажуть числа \(n\), \(k\) i \(q\).

Потім KABANу задають \(q\) запитань, в кожному запитанні дані два числа: \(g\) і \(s\).

Йому потрібно порахувати кількість чисел \(x\) від \(0\) до \(n\) включно таких, що \(\sum_{p=0}^{\infty} \lfloor \frac{x}{k^p} \rfloor = g (mod \: s)\).

Всі ми інколи трохи KABAN, але ви KABAN прямо зараз, тому порахуйте все як KABAN і виведіть відповідь на кожне запитання.

Input

У першому рядку задано три цілих числа \(n\), \(k\) та \(q\).

У наступних \(q\) рядках задано по два цілих числа: \(g\) та \(s\).

Output

Виведіть \(q\) рядків — відповіді на запитання у порядку, якому їх задавали.

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\) — просте число.

Samples

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