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?

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.

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.

input

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

3 1 0 4 2

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