Lazy Numbers

共有 $T$ 组数据。每组数据给定正整数 $n,k$，将 $1\sim n$ 化成 $k$ 进制后按照字典序从小到大排序。求排序后第 $i$ 个位置的 $k$ 进制数恰好为原来十进制下的 $i$ 的数量。 $T\leq 10^3,n,k\leq 10^{18}$。

You are given positive integers $ n $ and $ k $ . For each number from $ 1 $ to $ n $ , we write its representation in the number system with base $ k $ (without leading zeros) and then sort the resulting array in lexicographic order as strings. In the sorted array, we number the elements from $ 1 $ to $ n $ (i.e., indexing starts from $ 1 $ ). Find the number of values $ i $ such that the representation of number $ i $ is at the $ i $ -th position in the sorted array of representations. Examples of representations: $ 1 $ in any number system is equal to $ 1 $ , $ 7 $ with $ k = 3 $ is written as $ 21 $ , and $ 81 $ with $ k = 9 $ is written as $ 100 $ .

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^3 $ ) — the number of test cases. This is followed by a description of the test cases. The only line of each test case contains integers $ n $ and $ k $ ( $ 1 \leq n \leq 10^{18} $ , $ 2 \leq k \leq 10^{18} $ ).

For each test case, output a single integer — the number of values $ 1 \leq i \leq n $ such that the representation of number $ i $ in the number system with base $ k $ is at the $ i $ -th position after sorting.

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

In the first test case, for numbers $ 1 $ and $ 2 $ , their representations are at positions $ 1 $ and $ 2 $ respectively. In the second test case, the sorted array is $ [1_2 = 1, 10_2 = 2, 100_2 = 4, 11_2 = 3] $ , and only the representations of numbers $ 1 $ and $ 2 $ are at the required positions. In the third test case, the sorted array is $ [1_4 = 1, 10_4 = 4, 11_4 = 5, 12_4 = 6, 2_4 = 2, 3_4 = 3] $ , and only the number $ 1 $ is at its position.