Matriz prima
Usted tiene una matriz \(n × m\). La matriz consta de números enteros. En un movimiento, puede aplicar una transformación a la matriz: elija un elemento arbitrario de la matriz y auméntelo en 1. Cada elemento puede aumentarse un número arbitrario de veces.
Tiene mucha curiosidad por los números primos. Permítanos recordarle que un número primo es un entero positivo que tiene exactamente dos divisores enteros positivos distintos: él mismo y el número uno. Por ejemplo, los números son primos y los números no lo son.
Una matriz es prima si se cumple al menos una de las dos condiciones siguientes:
- la matriz tiene al menos una fila que solo contiene números primos;
- la matriz tiene al menos una columna que solo contiene números primos;
Su tarea es contar el número mínimo de movimientos necesarios para obtener una matriz prima a partir de la que tiene.
Entrada
La primera línea contiene dos números enteros - el número de filas y columnas en la matriz, correspondientemente.
Cada una de las siguientes n líneas contiene m enteros: la matriz inicial. Se cumple que para todo y .
Los números de las líneas están separados por espacios simples.
Salida
Imprima un solo entero: el número mínimo de movimientos necesarios para obtener una matriz prima a partir de la que tiene. Si tiene una matriz prima, imprima 0.
Puntuación
- Subtarea 1 (30 ptos): , .
- Subtarea 2 (70 ptos): Sin restricciones adicionales
Ejemplos
Ejemplo de entrada 1
3 3
1 2 3
5 6 1
4 4 1
Ejemplo de salida 1
1
Ejemplo de entrada 2
2 3
4 8 8
9 2 9
Ejemplo de salida 2
3
Ejemplo de entrada 3
2 2
1 3
4 2
Ejemplo de salida 3
0
Nota
En la primera muestra, debe aumentar el número en la celda . Así, la primera fila estará formada por números primos: .
En la segunda muestra, debe aumentar el número en la celda tres veces. Así, la segunda columna estará formada por números primos: .
En la tercera muestra no tiene que hacer nada ya que la segunda columna ya consta de números primos: .
Comments