Killjee and base X

★★★★★

1 votes

Combinatorics, Easy, Math

Details

Problem

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.

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

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