当前没有测试数据。

题目描述

CSL likes to study various functions. Recently, he became fascinated with a new function. He named it function. Its expression is as follows: $csl(p,x) = 3log_{p}x + 1$ Where p is a prime number. But CSL doesn't like floating point numbers and even numbers, nevertheless, he likes square numbers very much, so he decided to add some restrictions to his functions:

1.if is not integer，then let

2.if csl(p,x) is integer，but p is 2 or p can't be expressed as the sum of two squares（which means: ∄a,b∈N+,s.t. $\nexists a,b \in N^+,s.t. \ a^2+b^2=p∄a,b∈N+,s.t.$）,then let

TL saw the function of CSL. He thought it was not interesting enough, so he also defined a function: $tl(p,x)=max_{d|x}(csl(p,d))$ Where p is a prime number too. TL asked CSL proudly: I will give you an x, Could you calculate $\sum_{d|x}\prod_{p}tl(p,d)$ (in which p passing through all the prime numbers)?

CSL thought about it and told TL the answer quickly. and he asked TL：so if I give you a n , Could you calculate $\sum_{d=1}^{n}\prod_{p}tl(p,d)$ ?

TL can't do this, so he turned up to you for help.

输入格式

The first line of the input is a single integer $(T≤5)$ (T \leq 5)T(T≤5) indicating the number of test cases.

Each of the following lines contains one integer (meaning as description)

$T \leq 5$

$n \leq 10^{9}$

输出格式

For each test case, output the answer in a single line.

样例

样例输入 1

4
1
2
3
5

样例输出 1

1
2
3
8