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
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

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 ??


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