Hip-n is a game in which two players take turns by placing tokens on the free cells of a non-empty n × n checkerboard. The game is lost by the first player placing four tokens identifying the vertices of a square: they can be of any size and tipped at any angle. The game ends in a tie when the board is full of tokens and no player has lost. The following figure depicts a 6 × 6 checkerboard and three examples of squares: the first player putting four tokens on the vertices of any of these squares loses the game. Of course, there are many more options for losing a game in the 6×6 checkerboard. Your task is to create a program that decides the outcome of a Hip-n game described as a sequence of plays, by identifying the player that loses or recognizing a tie. Input The input consists of several test cases. It ends when there are no more cases to test. The first line of each test case contains an integer n (1 ≤ n ≤ 200) indicating the number of rows and columns of the checkerboard. The next line contains n2 distinct pairs of blank-separated integers r and c in the checkerboard (0 ≤ r < n and 0 ≤ c < n): each such a pair identifies the placement of a token at row r and column c by the corresponding player. You can assume that player 1 makes the first move, player 2 the second one, player 1 the third one, and so on. Output For each test case, print a single line with ‘0’ if the game ends in a tie, ‘1’ if player 1 loses, and ‘2’ if player 2 loses. Sample Input 3 101121020120001222 3 101121020120120022 3 102221001202112001 Sample Output 0 1 2