E. Friendly Gifts
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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:

  1. Each of the given arrays is good.
  2. 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.

Example
Input
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
Output
0
1
1
2
1
3
4
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$$$].