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 LL, you have to find the product of two different integers such that their LCM (Least Common Multiple) is LL and the product is maximum possible.

Input

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

The next TT lines contain an integer LL (2L10122 \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 10000000071000000007.

Sample

InputOutput
3
5
13
27
5
13
243

For the first test case, let two integers a=1a = 1 and b=5b = 5. LCM(a,b)=5LCM (a, b) = 5 and a×b=5a \times b = 5.

For the second test case, let two integers a=1a = 1 and b=13b = 13. LCM(a,b)=13LCM(a, b) = 13 and a×b=13a \times b = 13.

For the third test case, let two intergers a=9a = 9 and b=27b = 27. LCM(a,b)=27LCM(a, b) = 27 and a×b=243a \times b = 243. Another possible pair is a=3a = 3 and b=27b = 27. LCM(3,27)=27LCM(3, 27) = 27 but 3×27<9×273 \times 27 < 9 \times 27. So, the result should be 243243.


Discussion

Statistics


46% Solution Ratio

woolgathererEarliest, 8M ago

Deshi_TouristFastest, 0.0s

steinumLightest, 131 kB

mah20tShortest, 330B

Submit

Login to submit

Editorial

Lets, LCM of the numbers AAA &amp; BBB is equal to LLL and their prime factorizations are −-− A=p1a1...

Toph uses cookies. By continuing you agree to our Cookie Policy.