Problem Description

For a positive integer $x$, let $f(x,B)$ denote the sum of digits of $x$ in base $B$. We say a positive integer $p$ is $B$-good if and only if for every positive integer $q<p$, we have $f(p,B)\ge f(q,B)$.

Given positive integers $n$ and $B$, compute how many positive integers $\le n$ are $B$-good.

Input Format

This problem contains multiple test cases in a single test file.

The first line contains the number of test cases $T$.

The next $T$ lines each contain two positive integers $n,B$.

Output Format

Output $T$ lines. Each line contains one non-negative integer, the answer.

6
4 2
9 3
1000 2
1000 20
28238934 154154154154154
23389348458425 5

3
6
49
60
28238934
760

Hint

Sample Explanation

Here we only explain the output of the second query. In base $3$, the digit sums of $1,2,3,4,5,6,7,8,9$ are $1,2,1,2,3,2,3,4,1$, respectively. From this, it is easy to see that only $1,2,4,5,7,8$ are $3$-good, so the output is $6$.

Constraints

All testdata satisfy: $1\le T\le 10^5$, $1\le n\le 10^{18}$, $2\le B\le 10^{18}$.

• Subtask $1$ ($50$ points): $T\le 10^4$, $n,B\le 100$.
• Subtask $2$ ($30$ points): $B=2$.
• Subtask $3$ ($20$ points): no special constraints.

Translated by ChatGPT 5