310689: CF1870F. Lazy Numbers

F. Lazy Numberstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$.

Input

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}$).

Output

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.

ExampleInput

8
2 2
4 2
6 4
33 2
532 13
780011804570805480 3788
366364720306464627 4702032149561577
293940402103595405 2

Output

2
2
1
3
1
3789
1
7

Note

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.

题目大意：
给定两个正整数n和k。对于从1到n的每个数，我们将其以k为基数的表示形式写下（不包含前导零），然后将得到的数组按照字符串的字典顺序排序。在排序后的数组中，我们将元素从1到n编号（即索引从1开始）。找出满足表示形式为i的数在排序后的表示数组中位于第i个位置的i的值个数。

例如，任何进制中的1等于1，k=3时的7写作21，k=9时的81写作100。

输入数据格式：
第一行包含一个整数t（1≤t≤10^3），表示测试用例的数量。接下来是t个测试用例的描述。
每个测试用例仅一行，包含整数n和k（1≤n≤10^18，2≤k≤10^18）。

输出数据格式：
对于每个测试用例，输出一个整数，即满足1≤i≤n的i的个数，使得i在k进制下的表示在排序后位于第i个位置。

示例：
输入：
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

注意：
在第一个测试用例中，数字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位于其位置。题目大意： 给定两个正整数n和k。对于从1到n的每个数，我们将其以k为基数的表示形式写下（不包含前导零），然后将得到的数组按照字符串的字典顺序排序。在排序后的数组中，我们将元素从1到n编号（即索引从1开始）。找出满足表示形式为i的数在排序后的表示数组中位于第i个位置的i的值个数。 例如，任何进制中的1等于1，k=3时的7写作21，k=9时的81写作100。 输入数据格式： 第一行包含一个整数t（1≤t≤10^3），表示测试用例的数量。接下来是t个测试用例的描述。 每个测试用例仅一行，包含整数n和k（1≤n≤10^18，2≤k≤10^18）。 输出数据格式： 对于每个测试用例，输出一个整数，即满足1≤i≤n的i的个数，使得i在k进制下的表示在排序后位于第i个位置。 示例： 输入： 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 注意： 在第一个测试用例中，数字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位于其位置。