B'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 <= q t <= q 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 <= q n <= q 10^{18} , 2 <= q k <= q 10^{18} ). For each test case, output a single integer -- the number of values 1 <= q i <= q 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. '...