CODCHESS  Naya Shatranj (New Chess)
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 threaten each other.
A 'ghoda' located in square (a, b) can threaten 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
lumaks_69:
20220124 15:34:04
✍️ 

negativeiq_20:
20210407 19:12:11
The understanding of the word *OPTIMALLY* is the key to solve this adhoc problem. 

viroin:
20200917 17:45:10
just requires observation skills, observe first few cases and you will get the ac 

codeblast_123:
20191010 09:02:48
Very very easy..... 

aryan29:
20190601 00:09:57
Think of it mathematically without relying on pattern,question is good enough 

aryan29:
20190531 23:27:30
Good adhoc question Last edit: 20190601 00:10:29 

pandey101299:
20190321 05:40:36
my 50th 

pandey101299:
20190321 05:39:51
So easy


sonuverma:
20171018 16:28:47
Nothing to do in this problem. Just observe reasult for first 4 cases :D 

codiesam_007:
20170906 22:28:55
total wastage of time

Added by:  CSI 
Date:  20130927 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 