Петрик і Марічка, ходячи по черзі, грають в таку математичну гру: Задано декілька натуральних чисел. За один хід будь-яке одне з чисел потрібно зменшити на будь-який степінь двійки (\textbf{1 2 4 8 16 …}), так, щоб результат лишився невід’ємним. Програв той, хто не зміг зробити хід. Потрібно оцінити шанси Петрика, якщо він починає першим і кожен з гравців дотримується виграшної стратегії. \textit{\textbf{Вхідні дані:}} Перший рядок -- кількість тестів K (не більше 10). У наступних K рядках по декілька (не більше 100) чисел (не більших 1000) в кожному. Всі числові значення у файлі натуральні. \textit{\textbf{Вихідні дані:}} У єдиному рядку \textbf{K} чисел, записаних підряд без пропусків, \textbf{1} або \textbf{0} - відповідь на відповідний тест, де \textbf{1} - у Петрика є всі шанси виграти і \textbf{0} у випадку переваги Марічки.