- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- 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:
- If the tree has \(N\) vertices, the array has length \(2N\).
- Each vertex has a number (from \(1\) to \(N\)) which is written twice (but they may not be necessarily beside each other).
- Between the numbers of each vertex, the numbers in its subtree are written.
- 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