ngpin04 là một nhà thám hiểm địa chất nổi tiếng. Một hôm, ngpin04 thám hiểm trong hang và gặp được một bài toán rất hay được khắc trên một tảng đá như sau:

Cho số nguyên dương ~n~ ~(n \leq 10^{12})~. Hãy tìm tất cả cặp số nguyên dương ~(x,y)~ (~x\le y~) sao cho ước chung lớn nhất và bội chung nhỏ nhất của hai số đó lần lượt là ~n~ và ~n^2~, sau đó tính tổng các ~x+y~. Nói cách khác cần tính tổng ~\displaystyle \sum_{x\le y,gcd(x,y)=n,lcm(x,y)=n^2}x+y~.

Tuy là một nhà thám hiểm địa chất nhưng ngpin04 rất đam mê toán học, bạn hãy giúp cậu ấy giải bài toán này nhé!

Trong đó:

• Ước chung lớn nhất (ƯCLN) của hai số nguyên là số nguyên dương lớn nhất là ước số chung của hai số đó.
• Bội chung nhỏ nhất (BCNN) của hai số nguyên là số nguyên dương nhỏ nhất chia hết cho cả hai số đó.

Input

Dòng đầu tiên gồm số nguyên ~t~ ~(1 \leq t \leq 10)~ là số bộ test.

~t~ dòng tiếp theo mỗi dòng gồm 1 số nguyên ~n~ ~(1 \leq n \leq 10^{12})~.

Output

Với mỗi bộ test, in ra một số nguyên duy nhất là tổng cần tính trên một dòng, chia lấy dư cho ~10^9+7~.

Subtask

• ~40\%~ số test có ~n \leq 10^3~.

• ~30\%~ số test có ~n \leq 10^{6}~.

• ~30\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

3
2
3
4

Sample Output 1

6
12
20