Killjee is learning about representation of numbers in different bases. Pahi seeing this got jealous and gave killjee a very difficult problem.

Let's call \(a_i\) be number of digits in x-base representation of i.X-base representation is representation of a number in base x.

Killjee needs to find \(\displaystyle\sum_{i=0}^{n} {a_i}\) for given n and x.

INPUT CONSTRAINTS
\(1 \le t \le 10^3\) \(1 \le n \le 10^{15}\) \(1 \le k \le 10^4\)

INPUT FORMAT
First line of input contain a single integer t.t lines follow each containing two space separated integers n and k.

OUTPUT FORMAT
For each test case output a single integer, answer to the problem. Print integers as space separated integers on single line.