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

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