Bolas

Lobo tem $n$ bolas. Ele coloca elas numa linha e as colore. A cor da $i$-ésima bola é $a_i$.

Lobo pode fazer a seguinte operação qualquer número de vezes:

• Selecionar $i, j$ tal que $1 \le i < j \le n$ com $a_i = a_j$.
• Remover $a_i, a_{i+1}, \cdots, a_j$ da linha.

Qual é o máximo de bolas que o lobo consegue tirar?

Input

Cada teste contém multiplos casos testes. A primeira linha do input contém um inteiro $t (1 \le t \le 10^3)$- O número de casos testes. A descrição dos casos segue da seguinte maneira

A primeira linha contém um inteiro $n (1 \le n \le 2 \cdot 10^5)$- O número de bolas do Lobo.

A segunda linha contém $n$ inteiros $a_1, a_2, \cdots , a_n (1 \le a_i \le n)$ - A cor das bolas.

É garantido que a soma de $n$ sobre todos os casos testes não passa de $2 \cdot 10^5$.

Output

Para cada caso teste, imprima o número máximo de bolas que o lobo pode tirar.

Exemplo

4
3

Para submeter sua solução use esse link