Trong tiết học về số thập phân, các bạn học sinh đều thích các số thập phân hữu hạn vì chúng có thể viết ra được (dù phần thập phân có thể có ~10^{10^{18}}~ số, nhưng ít ra còn đỡ hơn vô hạn). Nhưng trái lại, vốn là một người luôn có ý tưởng đột phá, Hiếu lại thích các số thập phân vô hạn. Chính sự đột phá này đã giúp cậu thành công trong nhiều cuộc thi khi mà giúp cậu đưa ra được những ý tưởng táo bạo và độc đáo. Hiểu được cậu, kh0i cũng ra một bài toán để thử thách Hiếu:

• Cho số nguyên dương ~n~, đếm số cặp ~(a, b)~ ~(1 \le a, b \le n)~ thỏa mãn ~s = \dfrac{a}{b}~ là số thập phân vô hạn.

Vì hiểu rằng Hiếu tuy vậy nhưng rất lười nên kh0i chỉ bắt cậu tìm đáp án chia lấy dư cho ~10^9 + 7~, nhưng cậu phải trả lời câu hỏi này ~t~ lần. Các bạn hãy giúp Hiếu nhé!

Input

• Dòng đầu tiên gồm số nguyên dương ~t~ là số lượng câu hỏi.
• ~t~ dòng sau, dòng thứ ~i~ gồm duy nhất một số nguyên dương ~n~ là câu hỏi trong lần thứ ~i~.

Output

• In ra ~t~ dòng, dòng thứ ~i~ chứa duy nhất một số nguyên là đáp án cho câu hỏi thứ ~i~, chia lấy dư cho ~10^9 + 7~.

Subtask

• Trong tất cả các test, ~1 \le t \le 10~.
• Subtask 1 ~(40\%)~: Trong tất cả các câu hỏi, ~1 \le n \le 1000~.
• Subtask 2 ~(30\%)~: Trong tất cả các câu hỏi, ~1 \le n \le 10^6~.
• Subtask 3 ~(30\%)~: Trong tất cả các câu hỏi, ~1 \le n \le 10^{12}~.

Sample Input

3
4
6
20

Sample Output

3
8
204

Explanation

• Các cặp số thỏa mãn với ~n = 4~ là: ~(1, 3)~, ~(2, 3)~, ~(4, 3)~.
• Các cặp số thỏa mãn với ~n = 6~ là: ~(1, 3)~, ~(2, 3)~, ~(4, 3)~, ~(5, 3)~, ~(1, 6)~, ~(2, 6)~, ~(4, 6)~, ~(5, 6)~.