CODCHESS - Naya Shatranj (New Chess)

no tags 

A and B are playing a very interesting variant of the ancient Indian game 'shatranj(also known as chess)' on a 'maidaan'(chessboard) n×n in size.

They take turns to put game pieces called 'ghoda'(knight) so that no two 'ghodas'(knights) could threat each other.

A 'ghoda' located in square (a,b) can threat squares (a+1,b+2),(a-1,b+2),(a+1,b-2),(a-1,b-2),(a+2,b-1),(a+2,b+1),(a-2,b-1),(a-2,b+1).

The player who can't put a new 'ghoda' during his move loses. Find out which player wins considering that both players play optimally well and A starts.

Input

The first line contains integer T (1≤T≤10^4) — the number of 'maidaans' (boards), for which you should determine the winning player. Next T lines contain T integers ni (1≤ni≤10^5) — the sizes of the 'maidaans'(chessboards).

Output

For each ni×ni board print on a single line "0" if A wins considering both players play optimally well. Otherwise, print "1".

Example

Input:
2
2
1

Output:
1
0

hide comments
pandey101299: 2019-03-21 05:40:36

my 50th

pandey101299: 2019-03-21 05:39:51

So easy
Just observe first two to three cases and make pattern

sonuverma: 2017-10-18 16:28:47

Nothing to do in this problem. Just observe reasult for first 4 cases :D

codiesam_007: 2017-09-06 22:28:55

total wastage of time
these kind of questions must be avoided!

anubhav1772: 2017-07-17 16:01:24

Just need Observation..that's it

vengatesh15: 2017-01-19 12:05:12

Simple one..

aryanagal: 2016-07-14 07:34:29

SO many WA for missing the \n, such an easy problem! Thanks @anuveshkothari

dushyant_bgs: 2016-06-27 19:24:00

Just observe the pattern.

code_killerx: 2016-06-21 18:41:51

I agree with K0d1 this question was a waste of time

mcjoshi: 2016-02-28 10:34:47

I solved this considering we have infinite number of knights.
Was it meant to do same way!! just 10 lines in C


Added by:CSI
Date:2013-09-27
Time limit:0.186s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64