IE3 - Non-Square Free Numbers

no tags 

A positive integer k is called squarefree if k is not divisible by d2 for any d > 1

Input

The input contains one integer t denoting the number of test cases.  Each of the following t lines contain a single integer n, 1 ≤ n ≤ 1010

Output

Your program should output one integer per test case, the n-th non-squarefree number.

Example

Input:

1
10

Output:

27

 


hide comments
Robert Gerbicz: 2013-10-20 04:40:07

Almost duplication of: http://www.spoj.com/problems/SQFREE/ moved to tutorial.


Added by:acheron
Date:2013-10-20
Time limit:8s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ONTAK 2010