Longest Symmetric Subsequence

You are given a sequence of integers which represent color codes. Your task is to find the length of the longest symmetric subsequence within the given sequence. A subsequence is considered symmetric if it reads the same forwards and backwards.

The input consists of multiple test cases. For each test case, you are given an integer N, which is the length of the sequence, followed by N space-separated integers. You need to compute and output the length of the longest symmetric subsequence for each test case.

Note: The subsequence does not need to be contiguous.

The solution should read input from standard input (stdin) and output the answer to standard output (stdout).

inputFormat

The first line of input contains an integer T denoting the number of test cases. Then for each test case, the input is as follows:

• The first line contains an integer N, the number of elements in the sequence.
• The second line contains N space-separated integers representing the sequence.

All input is given via stdin.

outputFormat

For each test case, output a single integer – the length of the longest symmetric subsequence – on a new line. The output should be written to stdout.

## sample

2
7
1 4 5 9 4 1 1
5
1 2 3 2 1

5
5

</p>