Sereja wants to answer q queries. In each query, she is given a number N. She wants to find the number of ordered pairs (x, y) such that x and y are factors of N and x and y are coprime.
1 ≤ q ≤ 200000
1 ≤ N ≤ 500000
The contest does have an editorial available, but i am unable to understand how the described equation was obtained.
If N = p1a1 * p2a2 * p3a3.....pna2, where p1...pn are primes,
then the number of ordered pairs will be : (2*a1 + 1) * (2*a2 + 1 ) * (2*a3 + 1 ).......(2*an + 1 )