Tính căn

Thành là một học sinh giỏi Toán. Vì vậy những kiến thức cơ bản trong toán học như tính giai thừa, tìm ước số, khai căn, \(\dots\) đối với cậu là các bài toán dễ.

Nhưng hôm nay Thành nhận được bài toán lạ: "Tìm ước số lớn nhất của \(N!\) sao cho căn bậc ba của nó là một số nguyên" và Thành cũng không phải mất nhiều thời gian để đưa ra kết quả.

Để kiểm tra kết quả của Thành đưa ra có đúng hay không, bạn hãy viết chương trình giải bài toán trên để so sánh với kết quả mà Thành đưa ra.

Input

• Dòng đầu chứa số nguyên dương \(T \le 10\) là số lượng bài toán;

• \(T\) dòng sau, mỗi dòng chứa một số nguyên dương \(N\) thể hiện câu hỏi tương ứng \((N \le 10^5)\).

Output

Ghi ra đáp án gồm \(T\) dòng, mỗi dòng là câu trả lời cho câu hỏi tương ứng.

Vì kết quả có thể rất lớn nên các bạn chỉ cần đưa ra phần dư của nó khi chia cho \(10^9 + 7\).

Notes

Ta có \(T = 2\).

Bài toán \(1\) có giá trị \(N = 1\). Vì \(1! = 1\) nên ước số lớn nhất có căn bậc ba là số nguyên cũng bằng \(1\).

Bài toán \(2\) có giá trị \(N = 4\). Vì \(4! = 24\). Trong các ước số của \(24\) thì số \(8\) là ước lớn nhất có căn bậc ba là số nguyên.

Scoring

• (\(60\%\)) \(N \le 20\);

• (\(40\%\)) Không có ràng buộc gì thêm.