Tienes un teclado que solo contiene las teclas numéricas $0,1,2,\cdots,9$.

Para cualquier entero positivo $m$, está claro que siempre puedes teclear un entero positivo que sea múltiplo de $m$.

Ahora han arrancado $k$ teclas de dígitos enteros positivos de tu teclado, pero aún quieres teclear un entero positivo que sea múltiplo de $m$.

Entrada

Cada archivo de prueba contiene varios casos de prueba. La primera línea contiene un entero $T$ ($1\le T\le 5\times 10^4$), que indica el número de casos de prueba.

Para cada caso de prueba:

La primera línea contiene dos enteros positivos $m,k$ ($1\le m\le 10^7$, $0\le k\le 9$). Indican que, tras arrancar $k$ teclas, debes teclear un entero positivo que sea múltiplo de $m$.

La segunda línea contiene $k$ enteros positivos distintos $p_i$ ($1\le p_i\le 9$), que indican las teclas arrancadas.

Salida

Para cada caso de prueba:

Si existe una solución, imprime tus operaciones como varias operaciones de “pulsar el dígito $a$ un total de $b$ veces”:

En la primera línea imprime un entero $n$, que debe satisfacer $1\le n\le 100$ y representa el número de operaciones necesarias.

En cada una de las siguientes $n$ líneas imprime dos enteros $a,b$, que deben satisfacer $0\le a\le 9$, $1\le b\le 10^{18}$. Representan una operación de “pulsar el dígito $a$ un total de $b$ veces”.

Si no existe una solución, imprime una línea con $-1$.

Ejemplos

Entrada 1

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

Salida 1

2
1 3
0 1
-1

Nota

Para el primer caso de prueba del ejemplo, el entero positivo tecleado por las operaciones de la salida de ejemplo es $1110$; $1110=37\times 30$ es un múltiplo de $37$.