Два игрока играют в игру. Изначально на доске записано число $$$n$$$. Игроки ходят по очереди. Если текущее число, записанное на доске, больше $$$0$$$, за свой ход игрок может текущее число поделить на 2 с округлением вниз, либо вычесть 1 из текущего числа, но такой ход можно сделать только тогда, когда текущее число нечетное. (то есть $$$4$$$ за ход можно превратить в $$$2$$$, а $$$7$$$ в $$$3$$$ или в $$$6$$$). Игра продолжается, пока на доске не окажется число $$$0$$$. Игрок, который не может сделать ход, проигрывает(то есть тот игрок, который вынужден ходить тогда, когда на доске записано число $$$0$$$). Определите, кто выигрывает при оптимальной игре обоих игроков - тот, кто ходил первым, или тот, кто ходил вторым. Вам нужно ответить на $$$t$$$ независимых запросов. На каждый из них выведите $$$1$$$, если для данного $$$n$$$ выигрывает первый игрок, и $$$0$$$ иначе. Ответы на запросы выводите в том порядке, в котором они идут во входных данных.