Крош и Ежик играют в следующую игру. Изначально у них есть одна кучка из $n$ камней. Игроки ходят по очереди, Крош ходят первым. За свой ход игрок может из кучки выбрать любое число камней, являющееся точным квадратом, и выкинуть эти камни из кучки, при условии, что в кучке есть такое число камней. Например, игроки могут брать $1, 4, 9, 16, 25, 36, ...$ камней из кучки за раз(при условии, что такое количество камней есть в кучке). Проигрывает тот, кто не может сделать ход, то есть кто вынужден делать ход тогда, когда в кучке не осталось камней. По заданному числу $n$ определите, кто выиграет при оптимальной игре обоих игроков. Если выиграет Крош, выведите $1$, иначе выведите $0$. Вам необходимо ответить на $q$ независимых запросов, для каждого из них выведите ответ в отдельной строке, кто выиграет при данном $n$.
В первой строке дано число $1 \le q \le 10^5$ - количество запросов. В следующих $q$ строках содержатся сами запросы, в каждой строке - число $1 \le n \le 10^5$. Гарантируется, что все запросы различны.
Для каждого запроса выведите $1$, если выиграет Крош, и $0$, если Ежик.
Input:
Output: