There's an old game called He loves me... he loves me not. The person picks petals from the flower thinking about a special someone. At the end if the number of picked petals is odd the special someone is in love.
However, you ain't got no flowers, so you will be deciding if the number of factors of N is odd the special someone is in love.
For example, if N is 28, the factors are 1, 2, 4, 7, 14, 28, so the special someone is not in love.
However, if N is 4, the factors are 1, 2, 4, so the special someone is in love.
In order to prevent you from cheating, you will need to output results for a batch of Ns in each testcase.
T
N_1
N_2
...
N_T
(In the first line there is T, a positive integer not exceeding 100)
(T lines follows, the i'th line containing N_i, a positive integer not exceeding 1000000000, corresponding to the settings of the i'th query)
T lines, the i'th line with the answer to the i'th query (an integer 0 if the someone is not in love and 1 otherwise), followed by a newline character