Problem :

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.**

Constrainsts :

1 ≤ q ≤ 200000

1 ≤ N ≤ 500000

**PROOF THE PROBLEM IS NOT FROM AN ONGOING CONTEST**

The contest does have an editorial available, but i am unable to understand how the described equation was obtained.

**EDITORIAL**

Let's consider that solution to your problem is

F(N).I want to solve a bit simpler problem. Let's

N = p^a, wherepis a prime number.Let's consider that

xwill havep^0in it's factorisation, so we have(a+1)options to select power ofpin factorisation ofy.In other case (there are

asuch cases), we have only one option — select powerpequal0in factorisation ofy.It's

(a+1)+(a), soF(p^a) = (2*a+1).You can solve problem separately for every power of

p[i]in factorization ofN. And the answer forNis a multiplication ofF(p[i]^a[i]). (these can be proven by Dirichlet convolution if I'm not mistaken).