SP1477 PT07A - Play with a Tree

Hey, ACRush and Jelly are playing a game ! Let take a look at its rule: You are given a tree. Two players take turns cutting edges on a tree. Some nodes is on the "ground". When a player cuts an edge, all the edges that are no longer connected to the ground disappear. The player who can not take a move loses. ACRush plays first. Both of them are very good players. If you know state of the tree they are playing with, can you guess who will win?  Node 4 is on the ground.

Input consists of multiple test-cases. The first line contains one integer _t_ - number of cases (0 < _t_

For each case, output who will win the game. If ACRush wins, output _1_; otherwise, output 0 (Jelly wins). There is no blank line after each case.