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
gautam: 2016-10-10 20:47:55

easy one .

Min_25: 2016-07-25 14:00:49

@square1001
There is an algorithm that can compute the answer for N=10^11 in a few seconds.

Last edit: 2016-07-25 14:03:03
square1001: 2016-07-25 13:51:36

It's a nice problem.
It can calculate for sieve method like Eratosthenes's sieve.
The time complexity is O(n log log n + t).
I calculated for n<100,000,000 in 4.287 sec in Visual Studio :-)
Can you calculate for more big n?

yeasintamim: 2016-06-23 20:21:23

why TLE ??

surya2196: 2016-05-21 12:56:25

lolypop question

darkhire21: 2016-01-04 08:53:22

Nice problem ...!!

dragonemperor: 2015-10-19 12:17:22

AC in first go :)

ASHUTOSH DWIVEDI: 2015-09-19 00:07:05

O(n*(sqrt(n)/log(sqrt(n))*log(n))) is enough....

Last edit: 2015-09-21 20:03:53
:.Mohib.:: 2015-07-02 17:30:39

Really nice que!!

manu nigotia: 2015-06-21 21:59:55

Failed to realize, it was this easy a problem. AC after 5 TLEs.


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