Cho một số nguyên dương ~n~, hãy đếm số cặp ~(x, y)~ mà:

• ~1 \le x \le y \le n~.

• ~\gcd(x, n)\times\gcd(y, n)=\gcd(x\times 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^5~) 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

Sample Input 1

2
3
4

Sample Output 1

5
8

Notes

• Ở test ví dụ thứ 1: có các cặp ~(x,y)~ thỏa mãn là: ~(1,1),(1,2),(1,3),(2,2),(2,3)~.

• Ở test ví dụ thứ 2: có các cặp ~(x,y)~ thỏa mãn là: ~(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(3,3),(3,4)~.