Your Game
Petryk and Marichka are playing a turn-based mathematical game:
You start with several natural numbers. On each turn, a player must reduce one of these numbers by any power of two (e.g., 1, 2, 4, 8, 16, etc.), ensuring the result is non-negative. The player who cannot make a move loses. Your task is to determine Petryk's chances of winning if he goes first and both players use optimal strategies.
Input
The first line contains the number of test cases K (up to 10). Each of the following K lines contains a sequence of natural numbers (up to 100 numbers per line, each not exceeding 1000).
Output
Output a single line with K digits, either 1 or 0, representing the result for each test case. A 1 indicates that Petryk has a winning strategy, while a 0 means Marichka has the advantage. Write these digits consecutively without spaces.