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 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: 2022-01-24 15:34:04

✍️

negativeiq_20: 2021-04-07 19:12:11

The understanding of the word *OPTIMALLY* is the key to solve this adhoc problem.

viroin: 2020-09-17 17:45:10

just requires observation skills, observe first few cases and you will get the ac

codeblast_123: 2019-10-10 09:02:48

Very very easy.....

aryan29: 2019-06-01 00:09:57

Think of it mathematically without relying on pattern,question is good enough

aryan29: 2019-05-31 23:27:30

Good adhoc question

Last edit: 2019-06-01 00:10:29
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!


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