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:

Sample Tree

 

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 a1, a2, ..., a2N (1 ≤ ai ≤ 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

 


Added by:MRM
Date:2017-07-06
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:SBU Newbies Programming Contest 2017

hide comments
2019-12-17 13:16:33
cakewalk!
2019-01-07 17:27:34
WA in case 10...damnit
2018-05-23 08:30:00
@lilkhon5
if u is parent of v, then the sequence would look like this:
sequence = { ... u ... v ... v ... u ... }
2018-05-20 12:11:41
will anyone explain the third condition?
2018-03-03 10:28:55
@rkp no, the degree of vertex 3 is equal to 4. so, the degree of tree is equal to 4.
2018-01-23 09:25:10 rkp
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 ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.