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

---

• 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