SP32103 TREEDEGREE - Degree of a Tree

mrm\_196 always represents 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 on 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:  Tree = {1, 3, 2, 2, 4, 4, 5, 5, 3, 1} Tree = {1, 3, 4, 4, 2, 2, 5, 5, 3, 1} Tree = {1, 3, 5, 5, 4, 4, 2, 2, 3, 1} Tree = {1, 3, 2, 2, 5, 5, 4, 4, 3, 1} Tree = {1, 3, 4, 4, 5, 5, 2, 2, 3, 1} Tree = {1, 3, 5, 5, 2, 2, 4, 4, 3, 1} 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_ (1 T The first line of each test contains an integer _N_ (1 N The second line of each test contains 2_N_ integers _a_ $ _{1} $ , _a_ $ _{2} $ , ..., _a $ _{2N} $_ (1 a $ _{i} $ N) — the elements of his array. 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.