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

Обмеження: 5 сек., 256 МіБ

Грайливий кабанець 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 і виведіть відповідь на кожне запитання.

Вхідні дані

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

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

Вихідні дані

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

Обмеження

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 3 4 2 3 3 5 0 5 1 5	2 0 2 1