Luis ha estado trabajando con números muy grandes. Exhausto de ver tales números, decide jugar con ellos un poco. Tiene una lista de ~N~ dígitos decimales. Observa que:

• Hay exactamente un dígito 9.
• No hay dígitos 0.

Luis agrega un dígito 0 a la lista. Ahora, Luis realiza recorridos sobre los dígitos de la siguiente manera:

1. Comienza en el dígito 0.
2. Desde el dígito en la posición ~i~, puede saltar al dígito en la posición ~j~ si ~D[j] = D[i] + 1~ ó ~D[j] = D[i] - 1~, donde ~D[k]~ es el valor del dígito en la posición ~k~.
3. Termina el recorrido cuando llega al dígito 9.
4. Cada par de posiciones ~(i,j)~ puede usarse como transición una sola vez en total (sin importar el orden ni la dirección).
5. Repite el proceso hasta que no existan más recorridos posibles.

Tu tarea es ayudar a Luis a determinar la máxima cantidad de recorridos distintos que puede realizar.

Entrada

La primera línea contiene un entero ~T~ ~(1 \leq T \leq 1000)~, el número de casos de prueba.

Cada caso de prueba consiste en dos líneas:

• La primera línea contiene un entero ~N~ ~(1 \leq N \leq 10^5)~, la cantidad de dígitos.
• La segunda línea contiene ~N~ enteros ~d_1, d_2,..., d_N~ ~(1 \leq d_i \leq 9)~, los dígitos de la lista. Se garantiza que exactamente uno de ellos es 9 y ninguno es 0.

La suma de ~N~ sobre todos los casos de prueba no excede ~10^5~.

Salida

Para cada caso de prueba, imprime un entero: la máxima cantidad de recorridos que Luis puede realizar.

Ejemplo de Entrada

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

Ejemplo de Salida

0
0
1

Explicaciones

Primer caso: Los dígitos son ~{0, 1, 2, 3, 8, 9}~. Faltan los dígitos ~4, 5, 6, 7~, por lo que no es posible conectar el 3 con el 8. La respuesta es 0.

Segundo caso: Los dígitos son ~{0, 1, 1, 2, 2, 3, 8, 8, 9}~. Faltan los dígitos ~4, 5, 6, 7~, por lo que tampoco hay camino posible. La respuesta es 0.

Tercer caso: Los dígitos son ~{0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9}~. Todos los dígitos del 1 al 8 están presentes. El número máximo de recorridos está limitado por la existencia de un único camino desde 2 a 3. La respuesta es 1.