Very hard task

Positive integer А is called a divisor of В if A divides B without remainder. For example, integer 15 has 4 divisors: 1,3, 5, 15.

Write a program that will find whether particular number has even or odd number of divisors.

Input

The first line of input contains integer N (1 ≤ N ≤ 100), the second line contains N integers X_i (1 ≤ X_i ≤ 10^18). Integers are split by spaces.

Output

Output should contain N integers. і–th number should be 0 if number of divisors of X_i is even, and 1, if number of divisors of X_i is odd.

Examples