IOPC1204 - A function over factors

no tags 

A function f is defined over natural numbers as:

f(N) = ∑ di μ(di)

Here the summation is over di, all positive integers which are factors of N.

μ(n) is the Möbius function defined in the following way: If there exists a prime p such that p2 is a factor of n, then μ(n)=0. Otherwise, if n has an odd number of prime factors, μ(n)=-1. If not, μ(n)=1. Thus the first few values for μ(n) (starting from 1) are 1, -1, -1, 0, -1, 1, -1, 0...

Given an integer X (0 <= X <= 1012), find the smallest natural number N such that |f(N)|>X.

Input

The first line of the input contains T, the number of test cases (T <= 1000). Following this are T lines, each containing an integer X (0 <= X <= 1012) corresponding to the test case.

Output

For each test case in the input, output the smallest natural number N such that |f(N)|>X.

Example

Input:
2
1
2

Output:
3
5

hide comments
Piyush Kumar: 2016-07-20 05:51:57

Is it just me or the TL is a bit too tight?

[Lakshman]: 2015-01-09 20:33:10

Is it possible to get AC with Haskell?

raunakrocks: 2013-03-23 18:10:08

AC!! [spoiler removed]

Last edit: 2013-03-23 18:26:15

Added by:Raziman T V
Date:2012-01-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:http://www.codechef.com/IOPC2012/