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