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.
in base 2, 0 can be written as 0, 1 can be written as 1, 2 can be written as 10, 3 can be written as 11, 4 can be written as 100. so sum of total number of digits is 1+1+2+2+3=9
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor