1183 - SCU-C

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 35

Solved: 22

Description
A positive integer is said to be squarefree if it is divisible by no perfect square larger than 1.
For example, the first few squarefree numbers are {1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, ...}.
Can you tell me the K-th ( 1-indexed ) smallest squarefree number
Input
The first line of the input will be a integer to represent the number of test cases.
For each test case there is only one line contains only one integer K.
( 1 <= K <= 10^9 )
There is a blank line before each test case.
Output
For each test case output the answer on a single line:
The K-th smallest squarefree number.
sample input
6

1

2

7

1000

1234567

1000000000
sample output
1
2
10
1637
2030745
1644934081
hint
source
SCUPC
© 2015 HUST ACMICPC TEAM. All Right Reserved.