Căn bậc ba Trong lúc chờ Trang mặc cả tiền cước với DNTL Express, Thiên Ân tranh thủ dùng máy tính chỉnh sửa cho hoàn thiện đoạn nhạc sẽ được trình diễn vào buổi duyệt văn nghệ. Thật không may cho Ân, vỏ của chiếc ổ cắm trên bàn cậu lại rơi xuống đất như thường lệ kéo theo sự sập nguồn của cả chiếc máy tính với mớ file nhạc dở dang. Quá chán nản với việc nhặt lên và lắp lại như mọi lần, Ân quyết định sẽ mặc kệ chiếc vỏ và tin rằng mình vẫn có thể sử dụng ổ điện mà không cần tới nó. Ân nhờ Tri - chàng trai khéo tay nhất lớp - thử cắm dây sạc máy tính của cậu vào ổ điện mà không cần lắp vỏ nhựa vào trước. Tiếc thay, các định luật Vật lý học đã không ủng hộ Ân. Tri thấy trước mắt mình sầm tối và khi cậu có thể mở mắt trở lại, xung quanh đã không còn là lớp học mà chỉ người thân gia đình và các bạn trong lớp. Dù đôi bàn tay khéo léo đã bị bỏng nặng nhưng đột nhiên Tri lại có được một khả năng vô cùng kỳ dị sau vụ tai nạn: Cậu có thể thực hiện các phép tính nhân, chia và khai căn bậc ba trong tích tắc! Tri lấy bút viết lên những dải băng bó một dãy các giai thừa của các số tự nhiên \(0, 1, 2, 3, 4, 5...\) và nói rằng sẽ miễn truy cứu trách nhiệm Ân nếu như cậu có thể tìm ra ước số lớn nhất của một vài số trong dãy trên sao cho căn bậc ba của chúng là một số nguyên - Tri có thể dễ dàng kiểm nghiệm lại đáp số đó. Hãy giúp Thiên Ân thoát khỏi sự liên đới trong vụ tai nạn này nhé!

Chú thích: \(n\) giai thừa, ký hiệu là \(n!\), là tích của n số tự nhiên dương đầu tiên, ví dụ \(4!=1*2*3*4=24\).

Yêu cầu: Với mỗi số nguyên dương \(N\) mà Tri đưa ra, hãy giúp Thiên Ân tìm ra ướ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.

Input

• Dòng đầu chứa số nguyên \(T≤10\) biểu thị số câu hỏi của Tri.
• \(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.

Output:

• \(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\).

Ví dụ:

Input:

2
1
4

Output:

1
8

Ràng buộc:

• Có 50% số test ứng với 50% số điểm của bài có \(N≤15\);
• 50% số test còn lại ứng với \(N \leq 10^5\).