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
def factors(n):
    return reduce(list.__add__,
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))
t = long(raw_input())
while t:
    t-=1
    a = long(raw_input())
    b = []
    b = factors(a)
    b = list(set(b))
    b.sort()
    c = 1
    for i in xrange(len(b)-1):
        c*=b[i]
    c = str(c)
    print c[-4:]