E. Поставь Коня!
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
input.txt
вывод
output.txt

Петя и Гена играют в очень занимательную игру «Поставь Коня!» на шахматной доске размером 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) (некоторые из них могут находиться вне доски). Проигрывает тот, кто не может сделать ход. Определите, кто выиграет при оптимальной игре обоих, если первым ходит Петя.

Входные данные

В первой строке задано целое число T (1 ≤ T ≤ 100) — количество досок, для которых вам надо определить исход игры. В следующих T строках заданы T целых чисел ni (1 ≤ ni ≤ 10000) — размеры шахматных досок.

Выходные данные

Для каждой доски ni × ni выведите в отдельной строке «0», если при оптимальной игре выигрывает Петя, иначе выведите «1».

Примеры
Входные данные
2
2
1
Выходные данные
1
0