3secv

"Bă și când te gândești că chiar au făcut testele la joingraf..."

Cerință

După ce chiar s-au făcut testele la problema joingraph de la ultimul concurs RoAlgo, comisia a realizat că mai este nevoie de o problemă specială. Astfel, după îndelungi discuții, s-a ajuns la următoarea problemă:

Dându-se $t$ șiruri $a$ de $n$ numere, să se găsească lungimea celei mai lungi secvențe care conține maxim $3$ numere distincte. Un exemplu de astfel de secvență este: $9 \ 1 \ 0$.

Date de intrare

Pe prima linie este numărul $t$. Pentru fiecare test, pe prima linie se va afla $n$, reprezentând numărul de numere. Pe a doua linie se vor afla cele $n$ numere.

Date de ieșire

Pe prima linie se va afla lungimea maximă a unei secvențe de maxim $3$ numere distincte.

Restriții și precizări

• $1 \leq t \leq 1 \ 000$;
• $1 \leq n \leq 10^6$
• Suma lungimilor celor $t$ șiruri nu depășește $10^6$.
• $1 \leq a_i \leq 10^9$

Exemplu

stdin

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

stdout

6
4
4
6
3

Explicație

Secvența 4 7 4 2 4 7 conține $3$ numere distincte. Nu mai există nicio secvență de lungime mai mare decât $6$.