Вам даны натуральные числа \(n\) и \(k\). Для каждого числа от \(1\) до \(n\) выпишем его запись в системе счисления с основанием \(k\) (без ведущих нулей), а затем отсортируем получившийся массив в лексикографическом порядке как строки. В отсортированном массиве пронумеруем элементы от \(1\) до \(n\) (то есть индексация начинается с \(1\)). Найдите количество чисел \(i\) таких, что запись числа \(i\) оказалась на \(i\)-й позиции в отсортированном массиве записей.
Примеры записей: \(1\) в любой системе счисления равно \(1\), \(7\) при \(k = 3\) будет записано как \(21\), \(81\) при \(k = 9\) будет записано как \(100\).
Выходные данные
На каждый набор входных данных выведите одно целое число — количество чисел \(1 \leq i \leq n\) таких, что запись числа \(i\) в системе счисления с основанием \(k\) оказалась на \(i\)-й позиции после сортировки
Примечание
В первом наборе входных данных для чисел \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|