Bài 12: Tổng Ước Chung Lớn Nhất

Yêu cầu: Cho ~T~ truy vấn. Mỗi truy vấn chứa một số nguyên dương ~N~. Hãy tính tổng của tất cả các Ước chung lớn nhất (GCD) giữa các số từ ~1~ đến ~N~ với chính ~N~. Công thức: ~S(N) = \text{GCD}(1, N) + \text{GCD}(2, N) + \dots + \text{GCD}(N, N)~.

Giới hạn:

• ~1 \le T \le 10^5~
• ~1 \le N \le 10^6~
• Thời gian: 1.0s | Bộ nhớ: 256 MB

Dữ liệu vào (Input):

• Dòng đầu chứa số truy vấn ~T~.
• ~T~ dòng sau, mỗi dòng là một số nguyên dương ~N~.

Dữ liệu ra (Output):

• In ra ~T~ dòng, mỗi dòng là kết quả của ~S(N)~.

Ví dụ: Input:

1
6

Output:

15

(Giải thích: ~\text{GCD}(1,6) + \text{GCD}(2,6) + \text{GCD}(3,6) + \text{GCD}(4,6) + \text{GCD}(5,6) + \text{GCD}(6,6) = 1 + 2 + 3 + 2 + 1 + 6 = 15~.