P16605 [SYSUCPC 2025] Sum

**同学 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$ 行，每行一个整数，表示所求的最小数位和。

对于 $6$，数位和在二进制或三进制下取得最小值。对于 $7$，数位和在二进制或三进制下取得最小值。对于 $30$，数位和在五进制下取得最小值。 翻译由 DeepSeek V3.2 完成