eolymp
bolt
Try our new interface for solving problems
Problems

Своя гра

Своя гра

Time limit 1 second
Memory limit 64 MiB

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

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

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

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

Examples

Input example #1
2
2 1
5 3 2
Output example #1
10
Source III етеп Всеукраїнської олімпіади з інформатики в Житомирській обл. 2014-2015 р