P9002 [RC-07] Heartbeat

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

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 $T$ lines. Each line contains one non-negative integer, the answer.

**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