Hàm \(d(n)\) biểu thị số ước của một số nguyên \(n\). Ví dụ \(d(24) = 8\) (Các ước của \(24\) là \(1, 2, 3, 4, 6, 8, 12, 24\)).

Hàm \(f(n)\) biểu thị tổng số ước các ước của \(n\). Ví dụ \(f(24) = d(1) + d(2) + d(3) + d(4) + d(6) + d(8) + d(12) + d(24) = 30.\)

Cho số tự nhiên \(n\), hãy tính \(f(n!)\), trong đó \(n!= 1 \times 2 \times 3 \times ... \times n\)

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) \((T \le 10^6)\) ứng với số lượng bộ dữ liệu.
• \(T\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(n\) \((n \leq 10^6)\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa phần dư \(f(n!)\) cho \(10000007\) tương ứng với mỗi bộ test.

Sample Input

3
4
5
1

Sample Output

30
90
1

Ràng buộc

• \(30\%\) số test tương ứng với \(1 \le T \leq 10^3.\)
• \(70\%\) số test còn lại tương ứng với \(1 \le T \le 10^6.\)