Tú tienes una matriz de N × M. La matriz consta de números enteros. En un solo movimiento, se puede aplicar una sola transformación en la matriz: elige un elemento arbitrario de la matriz y aumentalo en 1. Cada elemento se puede aumentar un número arbitrario de veces.

Eres muy curioso acerca de los números primos. recuerda que un número primo es un entero positivo que tiene exactamente dos divisores enteros positivos distintos: a sí mismo y el número uno. Por ejemplo, los números 2, 3, 5 son primos y los números 1, 4, 6 no lo son.

Una matriz es de primos si al menos una de las dos condiciones siguientes se cumplen:

la matriz tiene al menos una fila con sólo los números primos.
la matriz tiene al menos una columna con sólo números primos.

Su tarea consiste en contar el número mínimo de movimientos necesarios para obtener una matriz de primos a partir de la que ya tienes.

Input

La primera línea del INPUT comienza con un número C que indica el número de casos del problema propuesto. (1 <= C <= 50)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

S : Una línea que contiene los datos N y M. ( 1 ≤ N , M ≤ 50) - el número de filas y columnas de la matriz, de manera correspondiente.

Cada una de las siguientes N líneas contiene M enteros (separados por un espacio) de la matriz inicial. Todos los elementos de la matriz son enteros positivos.
Todos los números en la matriz inicial no excedan 10 ^ 5.
Los números de las líneas están separadas por espacios.

Output

Imprimir un único entero, el número mínimo de movimientos necesarios para obtener una matriz de primos a partir de la que se te dá. Si tienes una matriz de que cumple alguna de las condiciones, entonces imprimir 0.

Entrada de ejemplo

Explicación

En la primera muestra es necesario aumentar el número 1 en la celda (1, 1). Por lo tanto, la primera fila consistirá de números primos: 2, 2, 3.

En la segunda muestra es necesario aumentar el número 8 en la celda (1, 2) tres veces. Por lo tanto, la segunda columna constará de números primos: 11, 2.

En la tercera muestra no se tiene que hacer nada, pues la segunda columna ya consta de los números primos: 3, 2.