提示: 欢迎访问OurACM平台。
Problem 1523 A Version of Nim

Accept: 116    Submit: 191
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Here we introduce a special version of the combinatoric game called Nim. This progressively finite take-away game involves 4 piles of stones on a table. In this game, the two players take turns removing at least one but at most 3 stones from exactly one of the piles. The player who takes the last stone from the table losses.

The configuration of an instance of this Nim game can be described with four nonnegative integers representing the sizes of these four piles. i.e., (p1, p2, p3, p4), where the k-th, (1≤k≤4), number pk representing the current size of the k-th pile.

A configuration of this Nim game is winnable if a player facing this configuration can always find a way to win the game. To write a program that plays the Nim game perfectly, we need to decide whether a given instance of the Nim game is winnable to the current player or not facing the given configuration. For example, the configuration (0,0,0,2) is winnable by removing one stone from the last pile; however, you can verify that neither (0,0,0,5) nor (2,2,0,0) is winnable. Further, to make the problem easier, we assume that the number of stones on each pile is at most 9.

Input

The first line contains n, the number of Nim game configurations, which can be as large as 10000. After n, there will be n lists of Nim game configurations; each line contains four integers p1,p2,p3 and p4. Note that 0≤p1, p2, p3, p4≤9 and p1+p2+p3+p4≥1.

Output

For each configuration appeared in the input, decide whether it is winnable or not. Output a single number‘1' if the instance is winnable; otherwise, output‘0'.

Sample Input

4 0 0 0 5 0 0 0 6 0 0 2 2 1 2 3 4

Sample Output

0 1 0 0

Source

FZU 2007 ICPC Qualification Round II

Submit  Back  Status  Discuss