eolymp
bolt
Try our new interface for solving problems
Problems

Simple game (RU)

Simple game (RU)

Time limit 1 second
Memory limit 64 MiB

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

Input data

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

Output data

В единственной сроке K чисел, записанных подряд без пробелов, 1 или 0 - ответ на соответствующий тест, где 1 - у Толи есть все шансы победить и 0 в случае победы Серёжи.

Examples

Input example #1
2
2 3 4
2 7
Output example #1
01