9028: Classical Problem?

One day, Bobo encountered the following problem:
Given two positive integers n (n > 1) and k (k > 2),calculate the sum of the digits of n in base k, denoted asfk(n). Formally, let the sequence (ao, a1,..., al) satisfy thefollowing conditions:
1.al!=0
2.VO<i<l , O<ai<k-1
3. sum (i=0~l)ai * k^i = n
lt can be proven that such a sequence (ao, a1, ..., a) isunique. You need to calculate fk(n)ai
“lt's a piece of cake!” Bobo quickly passed this problem and theropened the next one. The problem description seems familiar:
Given two positive integers n (n > 1) and K (K > 2), youneed to find a base k (2 < k < K) such that the sum of thedigits of n in base k is minimized. You only need to outputthe minimum value. Formally, you need to calculatemin min fk(n) (2<=k<=K)
Bobo fell into deep thought. Can you help him?

This problem has multiple test casesThe first line contains a positiveinteger T (1<T<50)，denoting thenumber of testcases
The only line of each test casecontains two integers n and K (1<n < 1036，2 < K < 1036).

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

In the first test case of the sampletest，you may choose k =3,and that f3(15)=3.It can be proven this isthe minimum possible value of fk(nover al1 2<k<4.)