CF1870F Lazy Numbers

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.

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.