# Problem was solved!

Input is consist of 1 ≤ *q* ≤ 2 * 10^{4} queries every of which are described with single positive integer *n* not exceeding 4 * 10^{6}.

Output is to print for each query: **Where:**

⌊*x*⌋ = whole part of number, i.e. max integer which's ≤ *x*

φ(*x*) is Euler Totient Function

OK, I can previously calculate phis of all numbers from 1 to 4 * 10^{6} and *P* _{ i} for any *i*, 1 ≤ *i* ≤ 4 * 10^{6} in *O*(*nlogn*), but what's then? I don't know how to further optimize solution, because it is TLE with *O*(*n*) complexity per query.

Please, help me!