• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• I’m sorry madam, but your son is abnormal.
• (She cries out loud) but why?
• He has a strange habit of storing a rooted tree, in a simple array.
• OMG!!! How did this happen to us? What should we do now?
• Well, you should find him a problem-solver. Maybe you can find one in newbies contest!!

mrm_196 always rewrites the rooted trees in a simple array, but the array holds four conditions:

1. If the tree has $N$ vertices, the array has length $2N$.
2. Each vertex has a number (from $1$ to $N$) which is written twice (but they may not be necessarily beside each other).
3. Between the numbers of each vertex, the numbers in its subtree are written.
4. Vertex 1 is always the root of the tree.

For example, he may store the following tree in one of these six ways:

Your task is pretty simple, find what he always wanted, THE DEGREE OF THE TREE!!!! Degree of a tree is the maximum degree of all its vertices.

ورودی

The first line of the input contains an integer $T$ — the number tests to answer. $$1 \leq T \leq 20$$

The first line of each test contains an integer $N$ — the number of vertices in the tree. $$1 \leq N \leq 100, 000$$

The second line of each test contains $2N$ integers $a_1, a_2, \dots, a_{2N}$ — the elements of his array. $$1 \leq a_i \leq N$$

It’s guaranteed that the given array always forms at least one valid tree.

خروجی

For each test, print a single integer in one line — the degree of the tree.

مثال‌ها

ورودی نمونه ۱

2
1
1 1
5
1 3 2 2 4 4 5 5 3 1

خروجی نمونه ۱

0
4