F. Ленивые числа
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны натуральные числа $$$n$$$ и $$$k$$$. Для каждого числа от $$$1$$$ до $$$n$$$ выпишем его запись в системе счисления с основанием $$$k$$$ (без ведущих нулей), а затем отсортируем получившийся массив в лексикографическом порядке как строки. В отсортированном массиве пронумеруем элементы от $$$1$$$ до $$$n$$$ (то есть индексация начинается с $$$1$$$). Найдите количество чисел $$$i$$$ таких, что запись числа $$$i$$$ оказалась на $$$i$$$-й позиции в отсортированном массиве записей.

Примеры записей: $$$1$$$ в любой системе счисления равно $$$1$$$, $$$7$$$ при $$$k = 3$$$ будет записано как $$$21$$$, $$$81$$$ при $$$k = 9$$$ будет записано как $$$100$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит целые числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$2 \leq k \leq 10^{18}$$$).

Выходные данные

На каждый набор входных данных выведите одно целое число — количество чисел $$$1 \leq i \leq n$$$ таких, что запись числа $$$i$$$ в системе счисления с основанием $$$k$$$ оказалась на $$$i$$$-й позиции после сортировки

Пример
Входные данные
8
2 2
4 2
6 4
33 2
532 13
780011804570805480 3788
366364720306464627 4702032149561577
293940402103595405 2
Выходные данные
2
2
1
3
1
3789
1
7
Примечание

В первом наборе входных данных для чисел $$$1$$$ и $$$2$$$ их записи на $$$1$$$ и $$$2$$$ будут на позициях соответственно.

Во втором наборе входных данных отсортированный массив равен $$$[1_2 = 1, 10_2 = 2, 100_2 = 4, 11_2 = 3]$$$, на нужных позициях только записи чисел $$$1$$$ и $$$2$$$.

В третьем наборе входных данных отсортированный массив равен $$$[1_4 = 1, 10_4 = 4, 11_4 = 5, 12_4 = 6, 2_4 = 2, 3_4 = 3]$$$, на своей позиции только число $$$1$$$.