Петя и Гена играют в очень занимательную игру «Поставь Коня!» на шахматной доске размером n × n. В этой игре ребята по очереди ставят на доску шахматных коней так, чтобы никакие два коня не находились под ударом друг друга. Под ударом шахматного коня, находящегося в клетке (r, c), находятся клетки (r - 1, c + 2), (r - 1, c - 2), (r + 1, c + 2), (r + 1, c - 2), (r - 2, c + 1), (r - 2, c - 1), (r + 2, c + 1) и (r + 2, c - 1) (некоторые из них могут находиться вне доски). Проигрывает тот, кто не может сделать ход. Определите, кто выиграет при оптимальной игре обоих, если первым ходит Петя.
Выходные данные
Для каждой доски ni × ni выведите в отдельной строке «0», если при оптимальной игре выигрывает Петя, иначе выведите «1».