Толя та Сергійко, ходячи по черзі, грають в таку математичну гру. Задано декілька натуральних чисел. За один хід будь-яке одне з чисел треба зменшити на значення простого числа, так, щоб результат лишився натуральним. Програв той, хто не зміг зробити хід. Потрібно оцінити шанси Толі, якщо він починає першим і кожен з гравців притримується виграшної стратегії.

Вхідні дані

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

Вихідні дані

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