F. Lazy Numbers
binary search; math
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.