is studying numeral systems. For a natural number , wants to know the smallest digit sum among the representations of in bases from to . For example, the natural number has a representation of in base , with a digit sum of , and a representation of in base , also with a digit sum of .
输入格式
There are multiple test cases.
The first line of input contains a positive integer , indicating the number of test cases.
The next lines each contain two positive integers .
输出格式
Output lines, each containing an integer, representing the smallest digit sum.
样例
样例输入 1
4
6 3
7 4
30 5
999967000273 999983
样例输出 1
2
3
2
3
数据范围与提示
For , the digit sum is minimized in base or base . For , the digit sum is minimized in base or base . For , the digit sum is minimized in base .
