Cúcara Mácara is a dominican game, played when a random pick is needed.

Our cucara macara is a hazard game with the following rules. The dealer puts three identical bowls down faced on the table, with a small ball underneath the first one. Then, he repeatedly selects a pair of bowls and swaps their positions. Finally, he asks you "Where is the ball?". You win if you point to the right bowl and lose otherwise.

You are writing the computer version of this game, and in this problem, you must write the module that determines the position of the ball after all the bowl swaps have been done.

You will be given all the swaps describing the swaps made, in order. Each element of swaps will be in the format "X-Y" (quotes for clarity), which means that the bowl in position X was swapped with the bowl in position Y. The positions are 1, 2 or 3. Your program must print the position of the bowl with the ball after all the swaps.

Input

The first line is the number of test cases T, then T test cases follow.

Each test case starts with N (1 ≤ N ≤ 50), the number of swaps written in a single line, after this, N lines follow. Each line formatted "X-Y", denoting that the bowls 'X' and 'Y' were swapped.

Constraints

X and Y are one of the numbers 1, 2 or 3.

Output

For each test case, print one single line, containing the bowl with the ball after all the swaps.

Example

Input:
2
2
1-2
3-1
4
3-1
2-3
3-1
3-2

Output:
2
3