Al DJ Saturday Nite le encanta escribir música para números de canciones y bailes improvisados en institutos de todo el mundo. No tiene miedo de hacer que su música sea salvaje y emocionante, aunque está simultáneamente bien estructurada, con una exposición, un desarrollo y una recapitulación.

Una canción puede representarse mediante una matriz de números enteros positivos, donde cada número entero es una nota.

El flujo de una canción se define como el mayor número entero positivo, ~k~, tal que la subsecuencia ~[1, 2, 3, ..., k-1, k, k, k-1, ..., 3, 2, 1]~ exista en la matriz.

Por ejemplo, la matriz ~[1, 4, 2, 3, 1, 3, 2, 3 1]~ contiene la subsecuencia ~[1, 2, 3, 3, 2, 1]~, por lo que su flujo es ~3~. Si no existe tal ~k~, el flujo de la canción es ~0~. Nótese que una subsecuencia de una matriz puede obtenerse borrando algunos elementos de de la matriz (posiblemente ninguno), sin cambiar el orden de los elementos restantes.

DJ Saturday Nite ha escrito muchas canciones, y necesita tu ayuda para determinar el flujo de cada una.

Tarea

Dada una canción, determinar su flujo.

Entrada

La primera línea de entrada contiene un único número entero positivo ~t \le 10~, que representa el número de canciones. Para cada canción, la primera línea de esa canción contiene un entero, ~n (1 \le n \le 10^5~), que representa el número de notas en la canción. La siguiente línea contiene ~n~ enteros, ~a_i (1 \le ai \le 10^5)~, que representan las notas de la canción, respectivamente.

Salida

Para cada canción, emite un solo entero en su propia línea: el flujo de la canción

Ejemplod de Entrada

3
9
1 4 2 3 1 3 2 3 1
5
1 3 4 2 1
6
5 4 3 2 1 2

Ejemplo de Salida

3
1
0