Stack Game
By Lucas Hermann Negri, UTFPR 
Brazil
By Lucas Hermann Negri, UTFPR Brazil
Claudio has created a new game called Stack Game, and wants to submit it to the next URI's game competition. Although very fun to play, the game seems to be too difficult to win. Claudio needs your help to evaluate if some game instances can be won.
The Stack Game is individual and it is played with three stacks, each one with the same initial number of cards. Each card has a integer value from 0 to 9. The player can, at any time, peek the value of any card but can only play with the cards on the top of the stacks. At each round, the player can remove any combination of cards from the top of the stacks (1, 2 or 3 cards), but only if the sum of their values is divisible by 3. The game is won when all cards are removed from the piles. If a card can not be removed, the game is lost.
The input is composed of many instances. Each instance is initiated with an integer N (0 ≤ N ≤ 100) that identifies the number of cards in each stack. The input ends with N = 0. Each one of the N lines in the sequence will have three integers A, B e C, that describes the numeric values of the cards on a level of the stacks (0 ≤ A, B, C ≤ 9). The stacks are described from top to bottom.
For each instance, write a line with the number 1 if the player can win the instance, or the number 0 if the instance is impossible.
| Sample Input | Sample Output |
|
2 |
1 |