Đếm số nguyên tố cùng nhau

Cho $T$ truy vấn. Mỗi truy vấn gồm hai số nguyên dương $n$ và $m$. Với mỗi truy vấn, hãy đếm số nguyên $x$ trong đoạn $[1,m]$ sao cho $gcd(x,n)=1$ (tức là $x$ nguyên tố cùng nhau với $n$).

Lưu ý rằng $m$ có thể khác $n$, nên đây không đơn thuần là hàm Euler $\phi (n)$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $T$ — số truy vấn.
• Mỗi dòng trong $T$ dòng tiếp theo chứa hai số nguyên $n$ và $m$.

Dữ liệu ra

In ra $T$ dòng, mỗi dòng là một số nguyên: số lượng $x\in [1,m]$ thỏa $gcd(x,n)=1$ của truy vấn tương ứng.

Ràng buộc

• $1\le T\le 2·{10}^4$
• $1\le n\le {10}^9$
• $1\le m\le {10}^9$

Ví dụ