Highways of Byteland

All submissions for this problem are available.
Problem Statement
Byteland is a very famous country, as we all know. Recently the new President of Byteland has announced a proposal to construct Highways between the cities of the country (sadly no Highways existed between any pair of cities). Byteland has an odd naming convention where the cities are identified with integers from 1 to N. The president estimates that the length of the highway between two cities i and j would be equal to gcd(i, j), if the highway is constructed.
Since the president hates the city numbered 1, there won’t be any highway construction between cities i and j if gcd(i, j)=1, despite knowing that this might leave some cities unreachable from another through Highway System. So the Highway Department proposes to construct highway between all pair of cities i and j (1 <= i, j <= N) with gcd(i, j)>1.
Mr. President wants to maximize the number of interconnected cities in his highway system while keeping the sum of all highway length as less as possible.
Being the CEO of Nibble Construction (The Highway construction Company), you decide to charge phi(x) to construct a road of length x.
Here phi(x) stands for Euler’s Totient Function.
Your task is to determine the amount A, the highway department will have to pay to Nibble Construction, if highways are build according to the President's wishes.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a single integer N(the number of cities).
Output
For each test case, output a single line containing A, the required answer to the problem.
Constraints
1 ≤ T ≤ 50
1 ≤ N ≤ 10^{7}
Example
Input: 2 8 9 Output: 5 7
Author:  savy1 
Tags  savy1 
Date Added:  27022015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 