SP16139 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 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.

The first line contains integer T (1

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