Let \(a_i\) be the number of digits in the x-base representation of \(i\). The x-base representation is the representation of a number in base \(x\).

Determine the \(\displaystyle\sum_{i=0}^{n} {a_i}\) for the provided \(n\) and \(x\).

Input format

• First line: A single integer \(t\)
• Each of the next \(t\) lines: Two space-separated integers \(n\) and \(k\)

Output format
For each test case, print a single integer that represents the answer to the question. Print the integers as space-separated integers on a single line.

Constraints

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