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, ... đố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 ~\text{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 ≤ 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 ≤ 10^5)~.

Output

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~.

Sample Input

2
1
4

Sample Output

1
8

Giải thích

Ta có ~T = 2~ (tương ứng với 2 bài toán):

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 số lớn nhất có căn bậc ba là số nguyên (căn bậc ba của ~8~ bằng ~2~).

Subtask

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~1 < N ≤ 20~;

• Có ~40\%~ số test ứng với ~40\%~ số điểm với các trường hợp còn lại.