(Được trích từ câu chuyện có thật của p2o2HuaGiaBao.)
Một hôm, cô giáo của p2o2HuaGiaBao giảng lý thuyết về phân tích thừa số nguyên tố trên trường. Vì anh ta cảm thấy quá dễ nên đã lấy bài khác ra làm. Khi cô giáo thấy điều đó, cô giáo liền gọi cho phụ huynh và cho anh ta viết bản kiểm điểm.
Sau đó, cô giáo liền cho một bài toán khó để kiểm tra anh ta. Mà lỡ cho bài khó quá, nên không biết làm như thế nào nhưng p2o2HuaGiaBao vẫn giải được bình thường. Các bạn hãy giúp cô giáo tính nhé!
Cho \(q\) truy vấn, mỗi truy vấn là một số nguyên dương \(k\) \((1\le k\le 10^{6})\). Hãy tính tổng các ước số của \(k\). Biết rằng ước của \(k\) là \(x\) khi và chỉ khi \(k\) \(\vdots\) \(x\). Vì kết quả có thể rất lớn nên bạn cần phải \(\text{mod}\) \(10^9+7\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(q\) \((1\le q\le 10^6)\)
• \(q\) dòng tiếp theo, mỗi dòng gồm \(1\) số nguyên dương \(k\) \((1\le k\le 10^6)\)

Output

• Gồm \(q\) dòng, với mỗi dòng là đáp án của bài toán.

Example

5
4
17
6
8
10

7
18
12
15
18

1
100

217