Cho số nguyên dương \(N\).

Tính giá trị biểu thức:

Nói cách khác, bạn hãy tính giá trị của biểu thức \(GCD(N,1^2) + GCD(N, 2^2) + .... + GCD(N,N^2)\).

Trong đó, \(GCD(a,b)\) chính là ước chung lớn nhất của \(a\) và \(b\).

Định nghĩa: Ước chung lớn nhất của hai số \(a\) và \(b\) là số nguyên
dương lớn nhất mà cả \(a\) và \(b\) đều chia hết.

Input

• Dòng đầu ghi \(q\) \((q \le 75)\) - số câu hỏi.
• \(q\) dòng tiếp theo, mỗi dòng ghi số nguyên dương \(N\) \((N \le 10^5)\).

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

2
1
2

1
3