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

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

hide comments
2015-02-23 00:12:32 Abhinandan Agarwal
Quite a fun , it was ... from .53 to 0.0 ..
2014-07-12 11:14:19 Harry Mathis
The input / output examples above show new lines. That coasts me firstable an nzec-error!

Last edit: 2014-07-12 11:40:25
2013-12-29 10:30:38 Mukund Kumar
Great problem...costed me 3 tle to realize what was needed... ;)
2013-12-29 10:30:38 Aniket Kumar
good question... :)
2013-12-29 10:30:38 wisfaq
Can this problem be made available for all languages?
I don't see any reason for the restrictions.

Edit:
seems that all dates of comments have been set to 29-12-2013.
Thanks for adding more languages.

Last edit: 2013-12-29 14:21:24
2013-12-29 10:30:38 Ouditchya Sinha
Awesome problem... Costed me 2 TLE's to realise what the problem setter wanted. :)
2013-12-29 10:30:38 god_father
awesome problem ....
2013-12-29 10:30:38 Vikas Kushwaha
nice way to frame question :)
2013-12-29 10:30:38 Nnavneetsinha
Awesome problem
2013-12-29 10:30:38 Jignesh
wasted time finding patterns in output.. when there is such a straight forward simple solution, nice problem :)

Last edit: 2012-12-09 06:25:55
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.