Highways of Byteland
All submissions for this problem are available.
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 inter-connected 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.
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).
For each test case, output a single line containing A, the required answer to the problem.
1 ≤ T ≤ 50
1 ≤ N ≤ 107
Input: 2 8 9 Output: 5 7
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.