#P1488E. Palindromic Doubles
Palindromic Doubles
Description
A 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 integers . Any integer value appears in no more than twice.
What is the length of the longest palindromic subsequence of sequence ?
The first line contains a single integer () — the number of testcases.
Then the descriptions of testcases follow.
The first line of each testcase contains a single integer () — the number of elements in the sequence.
The second line of each testcase contains integers ().
Any integer value appears in no more than twice. The sum of over all testcases doesn't exceed .
For each testcase print a single integer — the length of the longest palindromic subsequence of sequence .
Input
The first line contains a single integer () — the number of testcases.
Then the descriptions of testcases follow.
The first line of each testcase contains a single integer () — the number of elements in the sequence.
The second line of each testcase contains integers ().
Any integer value appears in no more than twice. The sum of over all testcases doesn't exceed .
Output
For each testcase print a single integer — the length of the longest palindromic subsequence of sequence .
Note
Here 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