CSL likes to study various functions. Recently, he became fascinated with a new function. He named it function. Its expression is as follows:

Where p is a prime number. But CSL doesn't like floating point numbers and even numbers, nevertheless, he likes square numbers very much, so he decided to add some restrictions to his functions:

1.if is not integer，then let

2.if csl(p,x) is integer，but p is 2 or p can't be expressed as the sum of two squares（which means: ）,then let

TL saw the function of CSL. He thought it was not interesting enough, so he also defined a function:

Where p is a prime number too. TL asked CSL proudly: I will give you an x, Could you calculate (in which p passing through all the prime numbers)?

CSL thought about it and told TL the answer quickly. and he asked TL：so if I give you a n , Could you calculate ?

TL can't do this, so he turned up to you for help.

The first line of the input is a single integer  indicating the number of test cases.

Each of the following  lines contains one integer  (meaning as description)

For each test case, output the answer in a single line.

4
1
2
3
5

1
2
3
8