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$