Петя и Маша, ходя по очереди, играют в такую математическую игру:

Задано несколько натуральных чисел. За один ход любое одно из чисел нужно уменьшить на любую степень двойки (1 2 4 8 16 ...) так, чтобы результат остался неотрицательным. Проиграл тот, кто не смог сделать ход. Нужно оценить шансы Пети, если он начинает первым и каждый из игроков придерживается выигрышной стратегии.

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

Первая строка — количество тестов K (не более 10). В следующих K строках по несколько (не более 100) чисел, не больше 1000 каждое. Все числовые значения в файле натуральные.

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

В единственной строке K чисел, записанных подряд без пробелов, 1 или 0 — ответ на соответствующий тест, где единица обозначает, что у Пети есть все шансы выиграть и 0 в случае преобладания Маши.