+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- + *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 ```

حل سؤال در بانک سؤالات