eolymp
bolt
Try our new interface for solving problems
Problems

n-th Square Free

n-th Square Free

Time limit 1 second
Memory limit 16 MiB

A positive integer is said to be squarefree if it is not divisible by any 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, ...}. Find the n-th smallest squarefree number.

Input data

The first line contains the number of tests t. Each of the next t lines contains one integer n (1n10^9).

Output data

For each test case print in a separate line the n-th smallest squarefree number.

Examples

Input example #1
3
10
100
1000
Output example #1
14
163
1637
Author Mykhaylo Medvedev