URI Online Judge | 2869

Talking about Divisor ...

By Ricardo Martins, IFSULDEMINAS BR Brazil

Timelimit: 1

1 is a divisor of 6. In addition to 1, it has 3 more divisors of 6: 2, 3 and 6. In total, 6 has 4 divisors, and it is the smallest number that has 4 divisors. Talking about divisor, given a number n, what is the smallest number that has n divisors?

Input

The input is composed of several test cases. The first line contains an integer C, with the total of test cases. The following C lines have an integer N (1 <= N <= 100).

Output

For each input test case in your program, you must print an integer containing the smallest number that has N divisors. Some values ​​will have relatively large numbers. In this way, print in the form of MOD 1000000007

Input Sample Output Sample

4
1
4
11
100

1
6
1024
45360