Giáo sư Wu Zi Mu đã tiếp tục ra bài tập cho học sinh lớp \(1\) như sau:

"Định nghĩa \(S(N)\) là tổng tất cả các ước nguyên dương của \(N\). Ví dụ: \(S(12)=1+2+3+4+6+12=28\)

Cho \(Q\) truy vấn, mỗi truy vấn gồm số nguyên dương \(N\). Tính \(S(N!^{3})\) mod \(1200000090\)"

Học sinh nghĩ mãi không ra. Các bạn hãy giúp học sinh trả lời \(Q\) truy vấn trên.

Input

• Gồm \(Q+1\) dòng:
  • Dòng đầu tiên gồm số \(Q\).
  • \(Q\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(N\).

Output

• Gồm \(Q\) dòng là kết quả của \(Q\) truy vấn theo thứ tự từ trên xuống dưới, in ra từng dòng.

Constraints

• \(1 \leq N \leq 4\cdot 10^{7}\)
• \(1 \leq Q \leq 10\)

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(N \leq 5, Q \leq 3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^{4}, Q \leq 10\).
• Subtask \(3\) (\(30\%\) số điểm): \(N \leq 10^{6}, Q \leq 10\).
• Subtask \(4\) (\(30\%\) số điểm): \(N \leq 4\cdot 10^{7}, Q \leq 4\), tổng các \(N\) trong \(Q\) truy vấn không quá \(4\cdot 10^{7}\).

Example

2
4 
3  

40920
600