Classical Problem?

题号：NC255853
时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

One day, Bobo encountered the following problem:

Given two positive integers $n$ $(n\geq 1)$ and $k$ $(k\geq 2)$ , calculate the sum of the digits of $n$ in base $k$ , denoted as $f_k(n)$ . Formally, let the sequence $(a_0,a_1,\dots,a_{\ell})$ satisfy the following conditions:

$a_{\ell}\neq 0$

$\forall 0\leq i\leq\ell,0\leq a_i\leq k-1$

$\sum\limits_{i=0}^{\ell}a_ik^i=n$

It can be proven that such a sequence $(a_0,a_1,\dots,a_{\ell})$ is unique. You need to calculate $f_k(n)=\sum\limits_{i=0}^{\ell}a_i$ .

“It's a piece of cake!” Bobo quickly passed this problem and then opened the next one. The problem description seems familiar:

Given two positive integers $n$ $(n\geq 1)$ and $K$ $(K\geq 2)$ , you need to find a base $k$ ( $2\leq k\leq K$ ) such that the sum of the digits of $n$ in base $k$ is minimized. You only need to output the minimum value. Formally, you need to calculate $\min\limits_{2\leq k\leq K}f_k(n)$ .

Bobo fell into deep thought. Can you help him?

输入描述:

This problem has multiple test cases. The first line contains a positive integer  , denoting the number of test cases.

The only line of each test case contains two integers  and  (, ).

输出描述:

For each test case, output an integer in one line, denoting the answer.

示例1

输入

复制

4
15 4
987654321 9
987654321 12345678
1 100

输出

复制

备注:

In the first test case of the sample test, you may choose , and that . It can be proven this is the minimum possible value of  over all .