Tổng ước chung lớn nhất

Cho $Q$ truy vấn. Mỗi truy vấn cho một số nguyên dương $n$, hãy tính

$$S(n)=\sum _{i=1}^n\sum _{j=1}^{n}gcd(i,j),$$

trong đó $gcd(i,j)$ là ước chung lớn nhất của $i$ và $j$.

Đáp số có thể rất lớn (tới khoảng $4·{10}^{13}$) nhưng không lấy theo modulo — hãy in ra giá trị nguyên chính xác.

Dữ liệu vào

• Dòng đầu chứa số nguyên $Q$ — số truy vấn.
• Dòng thứ hai chứa $Q$ số nguyên $n_1,n_2,\dots ,n_Q$ — tham số của từng truy vấn.

Dữ liệu ra

In ra $Q$ dòng, dòng thứ $k$ là giá trị $S(n_k)$.

Ràng buộc

• $1\le Q\le 10$
• $1\le n_k\le 2·{10}^6$
• Tổng các $n_k$ trên mọi truy vấn không vượt quá $2·{10}^6$.

Ví dụ