TREEDEGREE  Degree of a Tree
mrm_196 always represents 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 on 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:
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.
Input
The first line of the input contains an integer T (1 ≤ T ≤ 20) — the number tests to answer.
The first line of each test contains an integer N (1 ≤ N ≤ 100 000) — the number of vertices in the tree.
The second line of each test contains 2N 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.
Output
For each test, print a single integer in one line — the degree of the tree.
Example
Input: 2 1 1 1 5 1 3 2 2 4 4 5 5 3 1 Output: 0 4
Warning: large Input/Output data, be careful with certain languages
hide comments
sandilya1599:
20190705 10:36:29


sanchit_aga:
20190107 17:27:34
WA in case 10...damnit 

khoaph:
20180702 05:48:26
Last edit: 20180702 05:50:59 

mrm_196:
20180523 08:30:00
@lilkhon5


likhon5:
20180520 12:11:41
will anyone explain the third condition?


mrm_196:
20180303 10:28:55
@rkp no, the degree of vertex 3 is equal to 4. so, the degree of tree is equal to 4. 

rkp:
20180123 09:25:10
Hello. The degree of the tree in the second case(i.e {1 3 2 2 4 4 5 5 3 1}) should be 3 right ? 
Added by:  MRM 
Date:  20170706 
Time limit:  1s3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  SBU Newbies Programming Contest 2017 