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

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

hide comments
2017-07-17 16:01:24
Just need Observation..that's it
2017-01-19 12:05:12
Simple one..
2016-07-14 07:34:29
SO many WA for missing the \n, such an easy problem! Thanks @anuveshkothari
2016-06-27 19:24:00
Just observe the pattern.
2016-06-21 18:41:51
I agree with K0d1 this question was a waste of time
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
2016-02-18 15:57:37
Waste of time....Nothing to think.... (-_-) ...
2016-02-13 10:44:16
the test cases are not clear to understand the question well enough. can anyone tell me what will be the output for 3 and 4...?
2016-01-20 05:47:40
easy one

Last edit: 2016-01-20 05:50:27
2016-01-09 07:07:58 DEVVRAT GUPTA
lol...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.