# Almost Triple Deletions solution codeforces

Almost Triple Deletions solution codeforces-

You are given an integer 𝑛n and an array 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an.

In one operation, you can choose an index 𝑖i (1𝑖<𝑛1≤i<n) for which 𝑎𝑖𝑎𝑖+1ai≠ai+1 and delete both 𝑎𝑖ai and 𝑎𝑖+1ai+1 from the array. After deleting 𝑎𝑖ai and 𝑎𝑖+1ai+1, the remaining parts of the array are concatenated.

For example, if 𝑎=[1,4,3,3,6,2]a=[1,4,3,3,6,2], then after performing an operation with 𝑖=2i=2, the resulting array will be [1,3,6,2][1,3,6,2].

What is the maximum possible length of an array of equal elements obtainable from 𝑎a by performing several (perhaps none) of the aforementioned operations?

Input

Each test contains multiple test cases. The first line of input contains one integer 𝑡t (1𝑡10001≤t≤1000) — the number of test cases. The following lines contain the descriptions of the test cases.

The first line of each test case contains a single integer 𝑛n (1𝑛50001≤n≤5000) — the length of array 𝑎a.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖𝑛1≤ai≤n) — the elements of array 𝑎a.

It is guaranteed that the sum of 𝑛n across all test cases does not exceed 1000010000.

Output

For each testcase, print a single integer, the maximum possible length of an array of equal elements obtainable from 𝑎a by performing a sequence of operations.

Example

input

Copy
5
7
1 2 3 2 1 3 3
1
1
6
1 1 1 2 2 2
8
1 1 2 2 3 3 1 1
12
1 5 2 3 3 3 4 4 4 4 3 3


output

Copy
3
1
0
4
2

Note

For the first testcase, an optimal sequence of operations would be: [1,2,3,2,1,3,3][3,2,1,3,3][3,3,3][1,2,3,2,1,3,3]→[3,2,1,3,3]→[3,3,3].

For the second testcase, all elements in the array are already equal.

For the third testcase, the only possible sequence of operations is: [1,1,1,2,2,2][1,1,2,2][1,2][][1,1,1,2,2,2]→[1,1,2,2]→[1,2]→[]. Note that, according to the statement, the elements deleted at each step must be different.

For the fourth testcase, the optimal sequence of operations is: [1,1,2,2,3,3,1,1][1,1,2,3,1,1][1,1,1,1][1,1,2,2,3,3,1,1]→[1,1,2,3,1,1]→[1,1,1,1].

For the fifth testcase, the only reachable array of two equal elements is [4,4][4,4].