Only three handfuls!

There are three handfuls of pebbles. Vassya and Peter play a game, making moves in turns, and Peter always goes first. In one move, it is allowed to take any number of stones from one handful or same number from two handfuls . The winner is the one who will take the last stone. To determine which of them will win, if both during the game kept to the optimal strategy.

Input

The first line specifies the number of test cases T (1 ≤ T ≤ 20), and the subsequent T line set through the gap to 3 numbers - the number of pebbles in a handful of A, B, C.

(0 ≤ A, B, C ≤ 301 and A + B + C > 0).

Output

For each test case output one line 1 – if Peter wins, or 2 – if Vassya wins.

Examples