DCEPCA03 - Totient Extreme


Given the value of N, you will have to find the value of H. The meaning of H is given in the following code:

H=0;
For (i=1; i<=n; i++) {
    For (j=1; j<=n; j++) {
        H = H + totient(i) * totient(j);
    }
}

Totient or phi function, φ(n) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. That is, if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ k ≤ n for which gcd(n, k) = 1

Constraints

0 < T <= 50
0 < N <= 10^4

Input

The first line contains T, the number of test cases. It is followed by T lines each containing a number N .

Output

For each line of input produce one line of output. This line contains the value of H for the corresponding N.

Example

Input:
2
3
10

Output:
16
1024

hide comments
fairooj_04: 2020-04-29 13:40:57

Very easy, avoid the loops, it will get you TLE

alishahali1382: 2018-11-23 19:24:09

H=( phi(1) + phi(2) + phi(3) + ... + phi(n) )^2

itachi_2016: 2018-01-01 15:09:36

Cute ! Use long long it costed me one WA :(

sandeep_4141: 2017-10-09 08:07:38

AC in one go !!..

bolderic: 2017-08-21 13:14:31

it really leads me into a hole and ....

rohit9934: 2017-06-18 18:12:01

Study properties of ETF before attempting otherwise tle.Use pen paper to simplify.
Otherwise it's very easy.

Last edit: 2017-06-18 18:12:41
da_201501181: 2017-04-03 13:22:56

AC in one go..!! Very Easy..!!

Anand: 2017-01-24 11:21:23

Nope! It is not as easy as the comments here are describing. You will have to do some paper work, google around for the properties of phi function and then you will get the answer. Do not get carried away by those "too easy" comments! Happy Coding :)

kira28: 2017-01-06 20:14:53

int - WA
long -AC

cat_got_bored: 2016-12-02 22:01:14

AC in 0.0 :P Too easy really


Added by:dce coders
Date:2012-12-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP C99 HASK JAVA PAS-GPC PAS-FPC PYTHON PYTHON3 PY_NBC
Resource:Own Problem