Some children dream of bicycles, electric trains, or dollhouses. However, Bituś asked for something completely different in his letter to Santa Claus. His wish came true! The boy received a set for cutting out colorful models: scissors, a rectangular piece of paper (also called a sheet), and a set of crayons. Children do not know strange color names like "plum" or "purple," so the crayon colors are numbered with consecutive natural numbers.

Bituś colored the sides of the rectangle with colors 1, 2, 3, 4 in clockwise order. Then, he cut the initial rectangle into $N + 1$ smaller pieces. The entire operation consisted of $N$ steps. Each step involved taking one of the pieces, drawing a line segment connecting the midpoints of two sides with a crayon, and cutting the piece along the drawn segment. The crayon used in the $i$-th step had color $i + 4$, so both resulting smaller pieces have a side of color $i + 4$. (It can be proven that all pieces are convex figures, so each cut indeed created exactly two smaller pieces.)

Bituś wrote down the colors of the connected sides: in the $i$-th step, he connected sides with colors $a_i$ and $b_i$ with a segment. However, you suspect that at some point Bituś might have made a mistake. For a given sequence of steps $(a_i, b_i)$, find the length of the longest prefix of this sequence that is valid, i.e., Bituś could have performed such steps (cuts). Bituś hates repetitions, so each unordered pair $(a_i, b_i)$ appears at most once.

Input

The first line of input contains an integer $T$ ($1 \le T \le 5$) denoting the number of test cases.

The first line of the description of each test case contains an integer $N$ ($1 \le N \le 200$) denoting the number of steps performed. The next $N$ lines contain the descriptions of the steps: the $i$-th of these lines contains two distinct integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le i + 3$) representing the description of the $i$-th step. Within a test case, the given unordered pairs are distinct, meaning that for $i \neq j$, it is not the case that $(a_i = a_j \text{ and } b_i = b_j)$ or $(a_i = b_j \text{ and } a_j = b_i)$.

Output

For each test case, output a single integer on a new line – the length of the longest valid prefix of the sequence of steps given in that test case.

Examples

Input 1

2
4
3 1
1 5
4 6
2 4
5
3 4
1 2
5 6
1 5
8 7

Output 1

3
5

Note

Explanation of the example: The figure below shows how to obtain a valid prefix of length 3 for the first test case. Performing the fourth step is not possible because there is no piece that would contain sides of colors 2 and 4. Note that if the 1–5 cut had been performed in the right piece in the second step, the cut from the third step could not have been performed.