P16605 [SYSUCPC 2025] Sum

$\texttt{Student A}$ is studying numeral systems. For a natural number $n$, $\texttt{Student A}$ wants to know the smallest digit sum among the representations of $n$ in bases from $2$ to $R$. For example, the natural number $6$ has a representation of $(110)_2$ in base $2$, with a digit sum of $2$, and a representation of $(20)_3$ in base $3$, also with a digit sum of $2$.

There are multiple test cases. The first line of input contains a positive integer $T(1\leq T \leq 100)$, indicating the number of test cases. The next $T$ lines each contain two positive integers $n,R(2\leq n,R\leq 10^{12})$.

Output $T$ lines, each containing an integer, representing the smallest digit sum.

For $6$, the digit sum is minimized in base $2$ or base $3$. For $7$, the digit sum is minimized in base $2$ or base $3$. For $30$, the digit sum is minimized in base $5$.