Given an integer $L$, you have to find the product of two different integers such that their LCM (Least Common Multiple) is $L$ and the product is maximum possible.

Input

The first line contains an integer $T$ ($1 \leq T \leq 1000$), the number of test cases.

The next $T$ lines contain an integer $L$ ($2 \leq L \leq 10^{12}$), LCM of two different integers.

Output

For each test case, print the maximum possible product of those two integers. As the result can
be very big, print the result modulo $1000000007$.

Sample

Input	Output
3 5 13 27	5 13 243
For the first test case, let two integers $a = 1$ and $b = 5$. $LCM (a, b) = 5$ and $a \times b = 5$. For the second test case, let two integers $a = 1$ and $b = 13$. $LCM(a, b) = 13$ and $a \times b = 13$. For the third test case, let two intergers $a = 9$ and $b = 27$. $LCM(a, b) = 27$ and $a \times b = 243$. Another possible pair is $a = 3$ and $b = 27$. $LCM(3, 27) = 27$ but $3 \times 27 < 9 \times 27$. So, the result should be $243$.