Input is consist of 1 ≤ q ≤ 2 * 10⁴ queries every of which are described with single positive integer n not exceeding 4 * 10⁶.
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⁶ and P_i for any i, 1 ≤ i ≤ 4 * 10⁶ 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!