题目描述

同学 A 正在研究进制系统。对于一个自然数 $n$，同学 A 希望知道 $n$ 在从 $2$ 到 $R$ 的所有进制表示中，最小的数位和是多少。例如，自然数 $6$ 在二进制下的表示为 $(110)_2$，数位和为 $2$；在三进制下的表示为 $(20)_3$，数位和同样为 $2$。

输入格式

本题包含多组测试数据。

输入的第一行包含一个正整数 $T$（$1\leq T \leq 100$），表示测试数据的组数。

接下来的 $T$ 行，每行包含两个正整数 $n$ 与 $R$（$2\leq n,R\leq 10^{12}$）。

输出格式

输出共 $T$ 行，每行一个整数，表示所求的最小数位和。

4
6 3
7 4
30 5
999967000273 999983

2
3
2
3

提示

对于 $6$，数位和在二进制或三进制下取得最小值。对于 $7$，数位和在二进制或三进制下取得最小值。对于 $30$，数位和在五进制下取得最小值。

翻译由 DeepSeek V3.2 完成