Zeros Everywhere#13100
Sign in

Zeros Everywhere

1 second
256 megabytes

For two positive integers and (y \ge 2) , let f_y(x) be the number of digits equal to in the base- representation of (written without leading zeros). For example f_2(6)=1 since 6=(110)_2 , and f_3(9)=2 since 9=(100)_3.

We also define f_1(x)=0 , since in unary is written using ones only.

You're given an integer , evaluate

\sum_{x=1}^{n}\sum_{y=1}^{n} f_y(x)

Input

The first line contains a single integer (1 \le t \le 10^4) – the number of test cases.

The only line of each test case contains a single integer (1 \le n \le 10^6).

It's guaranteed that the sum of over all tests doesn't exceed 10^6.

Output

For each test case, output a single integer – the value of the sum.

Examples

Example 1

Loading
Loading

Note

In the first test case , has no zeros in any base , so the answer is .

In the second test case , the answer is :

  • Base contributes .

  • Base : 1=(1)_2 , 2=(10)_2 , 3=(11)_2 , 4=(100)_2 and we've 0+1+0+2=3 zeros.

  • Base : only 3=(10)_3 has a zero , so zero.

  • Base : only 4=(10)_4 has a zero , so zero.

and we've 0+3+1+1=5.

In the third test case , the answer is :

  • Base contributes .

  • Base : 2=(10)_2 , 4=(100)_2 , 5=(101)_2 , 6=(110)_2 and we've 1+2+1+1=5 zeros.

  • Base : 3=(10)_3 and 6=(20)_3 , so zeros.

  • Bases 4,5,6,7 : only y=(10)_y has a zero , so zero each , in total.

and we've 0+5+2+4=11.

Scoring

  1. Subtask ( points) : (1 \le \sum n \le 2000)

  2. Subtask ( points) : (1 \le \sum n \le 10^6)