# 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

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:

- (x ≤ u && y ≥ v) or (u ≤ x && v ≥ y)
- (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

Input | Output |
---|---|

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} ].

Login to submit