# Simple Game of Sticks

Problem #180

Tags: games puzzle

Who solved this?

This game have been puzzling me for about dozen years. Recently I encountered one of its variation once again - it was given as a part of exam for to-be-interns by some software corporation.

It is played between two participants. They lay several objects (matchsticks, little stones, coins) in a single line. This line can have several spaces, for example:

``````| | |    | | | |    | |
``````

Here are three groups, containing `3`, `4` and `2` sticks. At each move the player can take any `1` or `2` adjacent sticks (it is forbidden to take `2` sticks belonging to different groups). Of course some of the groups can split into smaller one after the move.

The person who is forsed to take the last stick - loses.

For example, the position shown above can evolve as following:

``````| | |    | | | |    - |         player A took 1 stick from the last group of 2

| | |    | - - |      |         player B took 2 sticks from the middle group of 4 (splitting it)

| - |    |     |      |         player A took 1 stick from the middle of group of 3
``````

After this move there are `5` separated sticks so any further moves would consist of taking a single stick - e.g. player `B` loses the game.

Obviously for each position it is predetermined whether it is `losing` or `winning` if both players keep optimal strategy. For example in this case player `B` could probably win if after the first move of `A` he would take `2` sticks from the first group, reducing position to `1 4 1` instead of `3 1 1 1`. Is it correct? Can you prove it?

Input data: will provide the number of testcases in the first line.
Next lines will contain a single test-case each - specifying a sequence of groups of (initially) adjacent sticks, e.g. `3 4 2` for the starting position proposed above.
There will be no groups larger than `7` sticks and average quantity of groups will be about `10`.
Answer: should contain for each position either `1` if it is `winning` or `0` otherwise.

Example:

``````7
1
1 1
1 1 1
4
2 2
3 3
1 4

0 1 0 0 0 0 1
``````

We call position `winning` if the first person to move can win if playing optimally and `losing` otherwise.

You need to login to get test data and submit solution.