E. Friendly Gifts

Source: Codeforces 2236E
Contest: Codeforces Round 1103 (Div. 3)
Time limit: 3 seconds
Memory limit: 512 megabytes

Statement

Arseniy decided to make his friends Dabir and Egor happy. For this, he decided to give each of them an array of numbers of the same length. An array $b$ is called good if its elements can be rearranged so that for all $i \gt 1$ the condition $b_i - b_{i - 1} = 1$ holds.

Arseniy wants Dabir and Egor to be able to play with these arrays. For this, the following conditions must be satisfied:

• Each of the given arrays is good.
• If you write one array after the other (in other words, concatenate them), the resulting array is also good.

Arseniy already has an array $a$ of length $n$. He plans to cut both arrays from $a$, that is, to choose two non-overlapping subsegments of the same length. Help Arseniy determine the maximum possible length of the resulting arrays.

Input

The first line contains a single integer $t$ $(1 \le t \le 1000)$ — the number of test cases.

Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ $(1 \le n \le 6000)$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le n)$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $6000$.

Output

For each test case, output a single integer — the maximum possible length of the arrays.

Note

In the first sample, it is impossible to select $2$ arrays, so the answer is $0$.

In the second sample, the maximum length of the selected arrays is $1$. Arrays [$1$] and [$2$] can be selected.

In the fourth sample, the maximum length of the selected arrays is $2$. You can select arrays [$2, 1$] and [$4, 3$].

In the fifth sample, the maximum length of the selected arrays is $1$. One way to select arrays is [$1$] and [$2$]. Other methods are arrays [$2$] and [$3$], [$3$] and [$4$], or [$4$] and [$5$].

Examples

7
1
1
2
1 2
3
2 1 1
4
2 1 4 3
5
1 2 4 5 3
6
3 2 1 6 5 4
10
1 1 2 3 4 1 6 5 7 8

0
1
1
2
1
3
4