LCM

By Ishtiaq · Limits 1s, 512 MB

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$ .

Input

Output

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$ .

	CPU	Memory	Source
Bash 5.0	1×	1×	1×
Brainf*ck	1×	1×	1×
C# Mono 6.0	1×	1×	1×
C++11 GCC 7.4	1×	1×	1×
C++14 GCC 8.3	1×	1×	1×
C++17 GCC 9.2	1×	1×	1×
C11 GCC 9.2	1×	1×	1×
Common Lisp SBCL 2.0	1×	1×	1×
Erlang 22.3	1×	1×	1×
Free Pascal 3.0	1×	1×	1×
Go 1.13	1×	1×	1×
Haskell 8.6	1×	1×	1×
Java 1.8	1×	1×	1×
Kotlin 1.1	1×	1×	1×
Node.js 10.16	1×	1×	1×
Perl 5.30	1×	1×	1×
PHP 7.2	1×	1×	1×
PyPy 7.1 (2.7)	1×	1×	1×
PyPy 7.1 (3.6)	1×	1×	1×
Python 2.7	1×	1×	1×
Python 3.7	1×	1×	1×
Python 3.8	1×	1×	1×
Ruby 2.6	1×	1×	1×
Swift 5.3	1×	1×	1×
Whitespace	1×	1×	1×