Với mỗi số nguyên dương ~N~, cần tìm ước số lớn nhất của ~N!~ sao cho ước số đó là một số lập phương. Vì kết quả có thể rất lớn, chỉ cần in phần dư khi chia cho ~10^9+7~.

Input

• Dòng đầu chứa số nguyên dương ~T~ ~(T \le 10)~.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~N~ ~(N \le 10^5)~.

Output

In ra ~T~ dòng, mỗi dòng là câu trả lời cho truy vấn tương ứng.

Subtask

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~1 < N \le 20~.
• Có ~40\%~ số test ứng với ~40\%~ số điểm có ~N \le 10^5~.

Ví dụ

2
1
4

1
8