Intellectual Games in Prostokvashino
Spring was on its way, and preparations were in full swing. Sharik was busy with his experiments, sawing non-standard chessboards and cutting out 2 squares from each, intending to use them for birdhouses later. Meanwhile, Matroskin and Pechkin spent their evenings playing dominoes. Matroskin soon discovered that Pechkin had three extra dominoes hidden up his sleeve (which ones exactly is left for the enthusiasts of this intriguing game to figure out). Being the clever cat he was, Matroskin confiscated the entire set along with the extra dominoes from Pechkin. In his spare time, while examining the dominoes, he noticed that one domino could perfectly cover two squares on Sharik's chessboards...
- Hmm, interesting, - mused the clever cat, - there are 31 dominoes, and after Sharik cuts out 2 squares, there are 62 squares left on the board. Can 31 dominoes completely cover such a board?
With plenty of boards and nothing else to do, Matroskin started organizing evening matches between Pechkin and Sharik: Sharik would cut out two squares from the chessboards, and Matroskin would hand them to Pechkin, challenging him to cover the board with dominoes. If Pechkin succeeded in covering the board, he won; if not, Sharik won.
Your task is to write a program that determines the winner in this intellectual game, given the coordinates of the squares Sharik cut out.
Input
The first line contains the number of boards Sharik cut, N (1 ≤ N ≤ 100). The next N lines each contain 4 numbers: the coordinates of the squares cut out on the current board.
Output
In a single line without spaces, output a sequence of 0 (Pechkin lost) and 1 (Pechkin won) based on the result of each chess-domino match between Sharik and Pechkin.