Nguồn: Tự nghĩ.
Rating : 1700.

**Đề Bài**:
Cubill nay được thầy 5Trứng dạy về hàm nhân tính. Do không chú ý nghe giảng nên cậu chỉ biết hàm $f(x)$ được gọi là hàm nhân tính nếu $f(x)*f(y)=f(x*y)$ với $gcd(x, y)=1$.

Về nhà cậu mở vở bài tập ra và chả hiểu gì nên cậu nhờ các bạn làm hộ cậu, bài tập về nhà của cậu như sau:

Cho một số nguyên dương $n$ hãy đếm số cặp $(x, y)$ mà:
* $x \le y$
* $1 \le x, y \le n$
* $gcd(x, n)*gcd(y, n)=gcd(x*y, n)$

Với hàm $gcd(x, y)$ là ước chung lớn nhất của $x, y$.

**Input**:
* Dòng đầu chứa số nguyên dương $T$ ($1\le T \le 10^6$) thể hiện số lượng test.
* $T$ dòng tiếp theo mỗi dòng chứa một số nguyên dương $n$ ($1\le n \le 10^5$)
**Output**:
* $T$ dòng mỗi dòng in ra một số nguyên dương duy nhất là kết quả của test tương ứng.

**Scoring:**

| Subtask | Điểm | Giới Hạn |
| -------- | -------- | -------- |
| 1 | 30 | $1\le T \le 50, 1\le n \le 500$
| 2 | 70 | Không có ràng buộc gì thêm |

**Lời Giải:**
Subtask 1:
Đề bài bảo làm gì ta làm theo.
ĐPT: ($T.n^2.logn$).
Subtask 2:
Ta có: $f(n)$ là số lượng số $x$ mà $x\le n, gcd(x, n)=d$.
Dễ thấy $f(n)=phi(n/d)$ nếu d là ước của n.
Gọi $a(i, j)$ là số cặp $(x, y)$ mà:
* $x \neq y$.
* $i*j$ là ước của $n$.
* $gcd(x, n)=i$.
* $gcd(y, n)=j$.
* $1 \le x, y \le n$

Ta có thể chứng minh rằng $a(i, j)=phi(n/i)*phi(n/j)$.

Gọi $b(i)$ là số cặp $(x, y)$ mà:
* $i^2$ là ước của $n$.
* $gcd(x, n)=i$.
* $gcd(y, n)=i$.
* $1 \le x, y \le n$

Ta có thể chứng minh rằng $b(i)=phi(n/i)*(phi(n/i)+1)/2$.
Vậy nên đáp án của bài này là:
$(\sum_{x, y \in d(n)} a(x, y))/2+\sum_{x \in d(n)} b(x)$.

Chú ý để có độ phức tạp này các bạn phải sàng ước và phi trước.
Đpt $(n.logn + \sum_{i=1}^{10^5} d(i)^2)$

**Code:** https://ideone.com/5Fhnr2