I. Sum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Student A is studying numeral systems. For a natural number $$$n$$$, 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

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

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

Example
Input
4
6 3
7 4
30 5
999967000273 999983
Output
2
3
2
3
Note

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