Problem Description

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

Input Format

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 Format

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

4
6 3
7 4
30 5
999967000273 999983

2
3
2
3

Hint

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