In this problem, the divisors of N do not include the number N itself. For example, if N=24, the divisors of N (excluding N) are 1, 2, 3, 4, 6 and 12. Thus, the product of divisors is 1x2x3x4x6x8x12=13824. Since the result may be very large, if the result has more than 4 digits, the program only needs to compute the last 4 digits of it.
Input:
The first line contains t, the number of test cases (about 300,000). Then t test cases follow.
Each test case contains a single integer N (1 ≤ N ≤ 500,000) whose product of divisors needs to be computed.
Output:
For each test case, print a single line containing the corresponding result of that test case.

Example
Sample Input:
6
3
4
12
25
957
10000

Sample Output:
1
2
144
5
7493
0000

见题面

见题面