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
nayeem_joy:
20190806 22:25:12
Using totient_sieve and a wonderful observation with pen and paper about the above summation :)


alishahali1382:
20181123 19:24:09
H=( phi(1) + phi(2) + phi(3) + ... + phi(n) )^2 

itachi_2016:
20180101 15:09:36
Cute ! Use long long it costed me one WA :(


sandeep_4141:
20171009 08:07:38
AC in one go !!.. 

bolderic:
20170821 13:14:31
it really leads me into a hole and .... 

rohit9934:
20170618 18:12:01
Study properties of ETF before attempting otherwise tle.Use pen paper to simplify.


da_201501181:
20170403 13:22:56
AC in one go..!! Very Easy..!! 

Anand:
20170124 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:
20170106 20:14:53
int  WA


cat_got_bored:
20161202 22:01:14
AC in 0.0 :P Too easy really 
Added by:  dce coders 
Date:  20121205 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  C CSHARP C++ 4.3.2 CPP C99 HASK JAVA PASGPC PASFPC PYTHON PYTHON3 PY_NBC 
Resource:  Own Problem 