Своя гра

Петрик і Марічка, ходячи по черзі, грають в таку математичну гру:

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

Вхідні дані

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

Вихідні дані

У єдиному рядку K чисел, записаних підряд без пропусків, 1 або 0 — відповідь на відповідний тест, де 1 — у Петрика є всі шанси виграти і 0 у випадку переваги Марічки.

Приклади