Given an integer n, we are interested in finding the minimum integer m no less than n, such that there exists a strictly increasing sequence n=b_1<...<b_t=m, and the multiple b_1b_2...b_t is a perfect square. Note in case that n is itself a perfect square, we can take m=n so that b_1=n is a perfect square.
First line contains an integer T(T<=100) denote the number of test cases. For each test case, there is an integer n(2<=n<=100000) in a single line.
For each test case, please output the desired number in a line.
When n=2, we can choose m=6 and by multiplying 2*3*6=36 is a perfect square.
Migrated from old NTUJ.
tmt514
| No. | Testdata Range | Score |
|---|