1566 . Perfect Squares I
Description
Given an integer n, we were 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. For example, n=2 we can choose b_1=n=2, b_2=3 and m=b_3=6 such that 2*3*6=36 is a perfect square. We denote m by m=S(n). (Ha, it’s just as simple as msn!)
But conversely, there exists some m such that the equation S(x)=m has no solution.
Given k, find the k-th smallest positive integer m_k which does not have any solution on S(x)=m_k.
Input Format
First line contains an integer T(T<=100) denote the number of test cases. For each test case, there is an integer k(1<=k<=100000) in a single line.
Output Format
For each test case, please output the number m_k.
Sample Input 1
3 1 2 3
Sample Output 1
2 3 5
Hints
Problem Source
Migrated from old NTUJ.
tmt514
Subtasks
| No. | Testdata Range | Score |
|---|