E. Palindromic Doublestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputA subsequence is a sequence that can be obtained from another sequence by removing some elements without changing the order of the remaining elements.A palindromic sequence is a sequence that is equal to the reverse of itself.You are given a sequence of n integers a_1, a_2, \dots, a_n. Any integer value appears in a no more than twice.What is the length of the longest palindromic subsequence of sequence a?InputThe first line contains a single integer t (1 \le t \le 1000) — the number of testcases.Then the descriptions of t testcases follow.The first line of each testcase contains a single integer n (1 \le n \le 250\,000) — the number of elements in the sequence.The second line of each testcase contains n integers a_1, a_2, \dots, a_n (1 \le a_i \le n).Any integer value appears in a no more than twice. The sum of n over all testcases doesn't exceed 250\,000.OutputFor each testcase print a single integer — the length of the longest palindromic subsequence of sequence a.ExampleInput
5
6
2 1 3 1 5 2
6
1 3 3 4 4 1
1
1
2
1 1
7
4 4 2 5 7 2 3
Output
5
4
1
2
3
NoteHere are the longest palindromic subsequences for the example testcases:   2 1 3 1 5 2  1 3 3 4 4 1 or 1 3 3 4 4 1  1  1 1  4 4 2 5 7 2 3 or 4 4 2 5 7 2 3 
5
6
2 1 3 1 5 2
6
1 3 3 4 4 1
1
1
2
1 1
7
4 4 2 5 7 2 3

5 4 1 2 3 
['*special problem', 'data structures', 'dp', '*2200']