Pentru un șir de n numere, să se găsească lungimea celei mai lungi secvențe care conține maximum 3 numere distincte. Un exemplu de astfel de secvență este: 9 1 0, dar un exemplu de secvență care nu respectă această regulă este 4 2 1 3 4.

Cerința

Dându-se t șiruri a de n numere, să se găsească lungimea celei mai lungi secvențe care conține maximum 3 numere distincte.

Date de intrare

Pe prima linie a fișierului de intrare 3secv.in se află 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

Fișierul de ieșire 3secv.out va conține t linii, linia i conținând lungimea maximă a unei secvențe de maximum 3 numere distincte pentru cel de-al i-lea șir dat la intrare.

Restricții și precizări

• 1 ≤ t ≤ 1000
• 1 ≤ n ≤ 1.000.000
• Suma lungimilor celor t șiruri nu depășește 1.000.000.
• 1 ≤ a[i] ≤ 1.000.000.000

Exemplu:

3secv.in

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

3secv.out

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.