# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# 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

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

### Statistics

49% Solution Ratio

woolgathererEarliest, 1M ago

steinumFastest, 0.1s

steinumLightest, 131 kB

MR.Jukerburg11Shortest, 503B