There is an infinite number of light bulbs in off position. At each phase of the game only those lamps are turned on (if they were off) or off (if they were on) which numbers are divisible by the phase number of the game.

Find the state of the n-th lamp after the n-th phase of the game.

Input

Initially you are given the number of test cases t (1 ≤ t ≤ 10). Each of the next t lines contains the number n (0 < n ≤ 105) of the game phase.

Output

Print t lines, each showing the state of the corresponding lamp: 0 - the lamp is off, 1 - the lamp is on.