Your Game#7381
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 (1 2 4 8 16...), 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.
The first line contains the number of test cases (up to ). Each of the following lines contains a sequence of natural numbers (up to numbers per line, each not exceeding ).
Output a single line with digits, either or , representing the result for each test case. A indicates that Petryk has a winning strategy, while a means Marichka has the advantage. Write these digits consecutively without spaces.
Example 1