Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Non-Overlapping Ranges

Limits: 1s, 512 MB

In programming, a range is referred to as a continuous segment that has a lower bound and an upper bound. For example, [2, 4] and [1, 100] are valid and [4, 1] is invalid.

Two ranges ( [u, v], [x, y] ) are called non-overlapping ranges of if one of the following conditions is satisfied:

  1. (x ≤ u && y ≥ v) or (u ≤ x && v ≥ y)
  2. (v ≤ x) or (y ≤ u)

You are given an array A of N integers. So, A has a total of (N*(N-1))/2 different ranges. Among them, a range (u,v) is valid if (1 ≤ u < v ≤ N) and (A[u] == A[v] ). Let’s say there are a total of K valid ranges in A. You have to find the largest subset of ranges from those K ranges, where every possible pair of ranges should be non-overlapping.

Input

Input starts with an integer T (1 ≤ T ≤ 100), denoting the number of test cases. Each case contains an integer N (1 ≤ N ≤ 100), denoting the number of elements of array A. The next line will contain N integers separated by spaces, denoting the elements of the array A. Each of these integers will be in the range between 1 to 100.

Output

For each case of input, print the maximum possible size of the subset. See the notes for more details.

Samples

InputOutput
7
5
1 1 1 1 1
3
1 2 1
9
1 1 2 2 2 1 1 2 2
6
1 1 2 2 1 1
5
1 2 3 4 5
5
1 2 2 2 2
5
1 2 2 1 2
7
1
9
6
0
5
3

Notes

For the last test case, only valid set is [ {2,3}, {2,5}, {3,5} ].

Discussion