Đếm cặp nguyên tố cùng nhau trên lưới

Cho $Q$ 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ố cặp $(i,j)$ thỏa mãn $1\le i\le n$, $1\le j\le m$ và $gcd(i,j)=1$ (tức $i$ và $j$ nguyên tố cùng nhau).

Dữ liệu vào

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

Dữ liệu ra

In ra $Q$ dòng, dòng thứ $k$ là đáp án của truy vấn thứ $k$.

Ràng buộc

• $1\le Q\le 10$
• $1\le n,m\le 2·{10}^6$
• Tổng của $min(n,m)$ trên tất cả các truy vấn không vượt quá $2·{10}^6$.
• Đáp án có thể lớn (tới khoảng $4·{10}^{12}$), hãy dùng kiểu số nguyên 64-bit.

Ví dụ