#P1488E. Palindromic Doubles

    ID: 2484 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 8 Uploaded By: Tags>*special problemdata structuresdp*2200

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 nn integers a1,a2,,ana_1, a_2, \dots, a_n. Any integer value appears in aa no more than twice.

What is the length of the longest palindromic subsequence of sequence aa?

The first line contains a single integer tt (1t10001 \le t \le 1000) — the number of testcases.

Then the descriptions of tt testcases follow.

The first line of each testcase contains a single integer nn (1n2500001 \le n \le 250\,000) — the number of elements in the sequence.

The second line of each testcase contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ain1 \le a_i \le n).

Any integer value appears in aa no more than twice. The sum of nn over all testcases doesn't exceed 250000250\,000.

For each testcase print a single integer — the length of the longest palindromic subsequence of sequence aa.

Input

The first line contains a single integer tt (1t10001 \le t \le 1000) — the number of testcases.

Then the descriptions of tt testcases follow.

The first line of each testcase contains a single integer nn (1n2500001 \le n \le 250\,000) — the number of elements in the sequence.

The second line of each testcase contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ain1 \le a_i \le n).

Any integer value appears in aa no more than twice. The sum of nn over all testcases doesn't exceed 250000250\,000.

Output

For each testcase print a single integer — the length of the longest palindromic subsequence of sequence aa.

Sample Input 1

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

Sample Output 1

5
4
1
2
3

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