C. Arrange the Numbers in a Circle

You have cards with numbers: $c_1$ cards with the number $1$, $c_2$ cards with the number $2$, ..., $c_n$ cards with the number $n$.

You must take at least three cards from the ones you have and arrange them in a circle so that the following condition holds:

• in every triple of consecutive cards, there are at least two equal cards. Formally, if the numbers on the chosen cards are $a_0, a_1, \dots, a_{k-1}$ in the order they are arranged in a circle, then the following condition must hold:

• for every $i$ from $0$ to $k-1$, there are at least two equal numbers among $a_i, a_{(i+1) \bmod k}, a_{(i+2) \bmod k}$. What is the maximum number of cards you can arrange?

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of two lines:

• the first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$);
• the second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_1 \le c_2 \le \dots \le c_n \le 10^9$). Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, output one integer — the maximum number of cards you can arrange. If it is impossible to choose three or more cards and arrange them in a circle so that the condition holds, output $0$.

ExampleNoteIn the first example, you can choose and arrange the cards as follows: $[4, 2, 4, 4]$. You cannot arrange more than $4$ cards. For example, the arrangement $[2, 4, 4, 1, 4]$ does not work, because the cards must be arranged in a circle, and the condition also applies to the triple consisting of the second-to-last, last, and first cards.

In the second example, you can arrange all the cards: $[1, 1, 2, 2, 2, 3, 3, 3, 3]$.

In the third example, you can choose and arrange the cards as follows: $[5, 5, 6, 6, 3, 6, 6, 5]$.

Input

InputThe first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of two lines:

• the first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$);
• the second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_1 \le c_2 \le \dots \le c_n \le 10^9$). Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

OutputFor each test case, output one integer — the maximum number of cards you can arrange. If it is impossible to choose three or more cards and arrange them in a circle so that the condition holds, output $0$.

Samples

3
4
1 1 1 3
3
2 3 4
3
1 1 2

4
9
3

Note

NoteIn the first example, you can choose and arrange the cards as follows: $[4, 2, 4, 4]$. You cannot arrange more than $4$ cards. For example, the arrangement $[2, 4, 4, 1, 4]$ does not work, because the cards must be arranged in a circle, and the condition also applies to the triple consisting of the second-to-last, last, and first cards.

In the second example, you can arrange all the cards: $[1, 1, 2, 2, 2, 3, 3, 3, 3]$.

In the third example, you can choose and arrange the cards as follows: $[5, 5, 6, 6, 3, 6, 6, 5]$.