You've got an n × m matrix. The matrix consists of integers. In one move, you can apply a single transformation to the matrix: choose an arbitrary element of the matrix and increase it by 1. Each element can be increased an arbitrary number of times.

You are really curious about prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors: itself and number one. For example, numbers 2, 3, 5 are prime and numbers 1, 4, 6 are not. 

A matrix is prime if at least one of the two following conditions fulfills:  the matrix has a row with prime numbers only;  the matrix has a column with prime numbers only; 

Your task is to count the minimum number of moves needed to get a prime matrix from the one you've got.


-----Input-----

The first line contains two integers n, m (1 ≤ n, m ≤ 500) — the number of rows and columns in the matrix, correspondingly.

Each of the following n lines contains m integers — the initial matrix. All matrix elements are positive integers. All numbers in the initial matrix do not exceed 10^5.

The numbers in the lines are separated by single spaces.


-----Output-----

Print a single integer — the minimum number of moves needed to get a prime matrix from the one you've got. If you've got a prime matrix, print 0.


-----Examples-----
Input
3 3
1 2 3
5 6 1
4 4 1

Output
1

Input
2 3
4 8 8
9 2 9

Output
3

Input
2 2
1 3
4 2

Output
0



-----Note-----

In the first sample you need to increase number 1 in cell (1, 1). Thus, the first row will consist of prime numbers: 2, 2, 3.

In the second sample you need to increase number 8 in cell (1, 2) three times. Thus, the second column will consist of prime numbers: 11, 2.

In the third sample you don't have to do anything as the second column already consists of prime numbers: 3, 2.

Source: codeforces | Difficulty: EASY
Tags: Number theory

Sorting

Mathematics

Complete search


Solutions:
import sys
import math
LIMIT = 100025
is_prime = [True for i in range(LIMIT + 1)]
distance_to_next_prime = [0 for i in range(200000)]

def sieve_of_eratosthenes():
	is_prime[0] = is_prime[1] = False
	for i in range(2, int(math.sqrt(LIMIT))):
		if is_prime[i]:
			j = 2
			while i * j <= LIMIT:
				is_prime[i * j] = False
				j += 1

def fill_next_primes():
	for i in range(LIMIT - 1, -1, -1):
		if is_prime[i]:
			distance_to_next_prime[i] = 0
		else:
			distance_to_next_prime[i] = 1 + distance_to_next_prime[i + 1]
sieve_of_eratosthenes()
fill_next_primes()
sizes_input = input().split(' ')
(n, m) = (int(sizes_input[0]), int(sizes_input[1]))
matrix = []
for i in range(0, n):
	matrix.append(input().split(' '))
moves = 100000
for index_row in range(n):
	best_row = 0
	for index_column in range(m):
		num = int(matrix[index_row][index_column])
		best_row += distance_to_next_prime[num]
	if best_row < moves:
		moves = best_row
for index_column in range(m):
	best_column = 0
	for index_row in range(n):
		num = int(matrix[index_row][index_column])
		best_column += distance_to_next_prime[num]
	if best_column < moves:
		moves = best_column
print(moves)


3
(n, m) = tuple(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
simple = [0] * (10 ** 5 + 4)
simple[1] = 1
for i in range(2, 10 ** 5 + 4):
	if simple[i] == 0:
		j = 2
		while i * j < 10 ** 5 + 4:
			simple[i * j] = 1
			j += 1
simple[-1] = len(simple) - 1
for i in range(10 ** 5 + 2, 0, -1):
	if simple[i] == 1:
		simple[i] = simple[i + 1]
	else:
		simple[i] = i
row = [0] * n
col = [0] * m
for i in range(n):
	for j in range(m):
		row[i] += simple[a[i][j]] - a[i][j]
		col[j] += simple[a[i][j]] - a[i][j]
print(min(row + col))


ncrivo = int(1000000.0)
crivo = [True for i in range(ncrivo)]
crivo[0] = False
crivo[1] = False
for i in range(2, ncrivo):
	if crivo[i]:
		for j in range(i ** 2, ncrivo, i):
			crivo[j] = False
(n, m) = map(int, input().split())
data = []
for i in range(n):
	data.append(list(map(int, input().split())))
contador = [0 for i in range(200000)]
contador[100000] = 3
for i in range(99999, -1, -1):
	if crivo[i]:
		contador[i] = 0
	else:
		contador[i] = 1 + contador[i + 1]
resultado = 100000
for i in range(n):
	soma = 0
	for j in range(m):
		soma += contador[data[i][j]]
	resultado = min(resultado, soma)
for i in range(m):
	soma = 0
	for j in range(n):
		soma += contador[data[j][i]]
	resultado = min(resultado, soma)
print(resultado)


import bisect

def primer():
	n = 100010
	li = [True for i in range(n)]
	li[0] = False
	li[1] = False
	prime = []
	for i in range(2, n):
		if li[i]:
			prime.append(i)
			for j in range(2, n):
				if i * j >= n:
					break
				li[i * j] = False
	return prime

def main():
	res = 987654321987
	prime = primer()
	(n, m) = map(int, input().split())
	li = []
	for i in range(n):
		x = list(map(int, input().strip().split()))[:m]
		li.append(x)
	for i in range(n):
		x = 0
		for j in range(m):
			pos = bisect.bisect_left(prime, li[i][j], 0, min(len(prime), li[i][j] + 10))
			x += prime[pos] - li[i][j]
		res = min(res, x)
	for j in range(m):
		x = 0
		for i in range(n):
			pos = bisect.bisect_left(prime, li[i][j], 0, min(len(prime), li[i][j] + 10))
			x += prime[pos] - li[i][j]
		res = min(res, x)
	print(res)
main()


from bisect import bisect_left as bl
(n, m) = map(int, input().split())
(pn, l) = ([], [])
q = 10 ** 5 + 4
k = [True for i in range(q + 2)]
for p in range(2, int(q ** 0.5) + 2):
	if k[p] == True:
		for i in range(p ** 2, q + 2, p):
			k[i] = False
for p in range(2, q + 1):
	if k[p]:
		pn.append(p)
for i in range(n):
	l.append(list(map(int, input().split())))

def f(l, q):
	for i in l:
		x = 0
		for j in i:
			x += pn[bl(pn, j)] - j
		q = min(q, x)
	return q
print(f(zip(*l), f(l, q)))


def Sieve():
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
n = 10 ** 5 + 12345
prime = [True for i in range(n + 1)]
Sieve()
(n, m) = [int(j) for j in input().split()]
M = []
for i in range(n):
	r = [int(j) for j in input().split()]
	for j in range(m):
		t = r[j]
		while True:
			if prime[t]:
				r[j] = t - r[j]
				break
			t += 1
	M.append(r)
ans = 12345678901231234
for i in range(n):
	if ans > sum(M[i]):
		ans = sum(M[i])
for j in range(m):
	sum = 0
	for i in range(n):
		sum += M[i][j]
	if ans > sum:
		ans = sum
print(ans)


import sys
import math
limit = 100025
primeNumberList = [True for i in range(limit + 1)]
distanceToNextPrimeNumber = [0 for i in range(200000)]

def sieve():
	primeNumberList[0] = primeNumberList[1] = False
	for i in range(2, int(math.sqrt(limit))):
		if primeNumberList[i]:
			j = 2
			while i * j <= limit:
				primeNumberList[i * j] = False
				j += 1

def getNextPrimeNumber():
	for i in range(limit - 1, -1, -1):
		if primeNumberList[i]:
			distanceToNextPrimeNumber[i] = 0
		else:
			distanceToNextPrimeNumber[i] = 1 + distanceToNextPrimeNumber[i + 1]
sieve()
getNextPrimeNumber()
dados = input().split(' ')
(n, m) = (int(dados[0]), int(dados[1]))
matrix = []
for i in range(0, n):
	value = input()
	matrix.append(value.split(' '))
rows = [0] * n
columns = [0] * m
for i in range(n):
	for j in range(m):
		num = int(matrix[i][j])
		distance = distanceToNextPrimeNumber[num]
		rows[i] += distance
		columns[j] += distance
rows_min = min(rows)
column_min = min(columns)
print(min(rows_min, column_min))


(n, m) = map(int, input().split())
s = [[*map(int, input().split())] for _ in ' ' * n]
limit = int(100000.0 + 2)
l = [1, 1] + [0] * limit
for i in range(2, limit):
	l[i * i::i] = [1] * ((limit - i * i) // i + 1)
for i in range(limit, -1, -1):
	l[i] *= l[i + 1] + 1
for i in range(n):
	for j in range(m):
		s[i][j] = l[s[i][j]]
print(min(min((sum(i) for i in s)), min((sum(i) for i in zip(*s)))))


def generate_primes(n):
	(primes, sieve) = ({}, [True] * int(n + 1))
	for p in range(2, n + 1):
		if sieve[p]:
			primes[p] = p
			for i in range(p * p, n + 1, p):
				sieve[i] = False
	return primes

def distance_prime(n, primes):
	if primes.get(n):
		return 0
	m = n + 1
	while not primes.get(m):
		m += 1
	return m - n
primes_dict = generate_primes(100100)
(x, y) = [int(x) for x in input().split(' ')]
columns = []
minimumOp = 10000000
for i in range(x):
	line = [distance_prime(int(x), primes_dict) for x in input().split(' ')]
	sumX = 0
	if i == 0:
		columns = line
	for j in range(len(line)):
		sumX += line[j]
		if i != 0:
			columns[j] += line[j]
	if sumX < minimumOp:
		minimumOp = sumX
minColumn = min(columns)
if minColumn < minimumOp:
	minimumOp = minColumn
print(minimumOp)


import math
import sys

def get_primes_distances(limit):
	distances = [0] * (limit + 1)
	sieve = [True] * (limit + 1)
	sieve[0] = False
	sieve[1] = False
	i = 2
	while i * i <= limit:
		if sieve[i] == True:
			for j in range(i * 2, limit + 1, i):
				sieve[j] = False
		i += 1
	distances[100000] = 3
	for i in range(99999, -1, -1):
		if not sieve[i]:
			distances[i] = distances[i + 1] + 1
	return distances
distances = get_primes_distances(100000)
input = sys.stdin
[n, m] = list(map(int, input.readline().strip().split()))
matrix = []
min_result = 10 ** 5
for i in range(n):
	matrix.append(list(map(int, input.readline().strip().split())))
rows = [0] * n
columns = [0] * m
for i in range(n):
	for j in range(m):
		gap = distances[matrix[i][j]]
		rows[i] += gap
		columns[j] += gap
rows_min = min(rows)
rows_column = min(columns)
print(min(rows_min, rows_column))


import bisect
from math import sqrt
maxn = int(100000.0 + 50)
isprime = [1 for i in range(maxn + 1)]
d = [1000000000.0 for i in range(maxn + 1)]

def sieve():
	cross_limit = int(sqrt(maxn))
	isprime[0] = isprime[1] = 0
	for i in range(4, maxn + 1, 2):
		isprime[i] = 0
	for i in range(3, cross_limit + 1, 2):
		if isprime[i]:
			for j in range(i * i, maxn + 1, 2 * i):
				isprime[j] = 0
sieve()
dst = 0
for i in range(maxn, 0, -1):
	if isprime[i]:
		dst = 0
	d[i] = min(d[i], dst)
	dst += 1
(n, m) = list(map(int, input().split()))
matrix = [list(map(int, input().split())) for i in range(n)]
rows = (sum([d[x] for x in matrix[i]]) for i in range(n))
column = (sum((d[matrix[i][j]] for i in range(n))) for j in range(m))
print(min(min(rows), min(column)))


import math
(n, m) = map(int, input().split())
matriz = [[*map(int, input().split())] for _ in ' ' * n]
(primos, prox_primo) = ([], [0] * 100100)

def eh_primo(x, primos):
	for i in primos:
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True
for i in range(2, 100100):
	if eh_primo(i, primos):
		primos.append(i)
(prox_primo[0], prox_primo[1]) = (2, 2)
for i in primos:
	primo = i
	while prox_primo[i] == 0:
		prox_primo[i] = primo
		i -= 1
soma_min_linhas = math.inf
for i in range(n):
	soma = 0
	for j in range(m):
		num = matriz[i][j]
		if prox_primo[num] == num:
			soma += 0
		else:
			soma += prox_primo[num] - num
	soma_min_linhas = soma if soma < soma_min_linhas else soma_min_linhas
soma_min_colunas = math.inf
for i in range(m):
	soma = 0
	for j in range(n):
		num = matriz[j][i]
		if prox_primo[num] == num:
			soma += 0
		else:
			soma += prox_primo[num] - num
	soma_min_colunas = soma if soma < soma_min_colunas else soma_min_colunas
print(min(soma_min_linhas, soma_min_colunas))


import math

def prime_filter(n, isPrime):
	for i in range(2, int(math.sqrt(n)) + 1):
		if isPrime[i]:
			for j in range(i * i, n + 1, i):
				isPrime[j] = False
	return isPrime

def minStep(matrix, nextPrime):
	cols = [0 for i in range(len(matrix[0]))]
	rows = [0 for i in range(len(matrix))]
	for r in range(len(matrix)):
		for c in range(len(matrix[r])):
			cur = matrix[r][c]
			add = nextPrime[cur] - cur
			rows[r] += add
			cols[c] += add
	print(min(min(rows), min(cols)))
(r, c) = [int(i) for i in input().split()]
matrix = []
for i in range(r):
	matrix.append([int(i) for i in input().split()])
n = 10 ** 5 + 1000
isPrime = [True for i in range(n + 1)]
isPrime = prime_filter(n, isPrime)
isPrime[1] = False
isPrime[0] = False
nextPrime = [0 for i in range(len(isPrime))]
index = 0
i = len(isPrime) - 1
while i >= 0:
	if isPrime[i]:
		index = i
	nextPrime[i] = index
	i -= 1
minStep(matrix, nextPrime)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def BS(val):
	(i, j) = (0, len(prime) - 1)
	ans = -1
	while i <= j:
		mid = (i + j) // 2
		if prime[mid] < val:
			i = mid + 1
		else:
			ans = mid
			j = mid - 1
	return ans
maxN = 10 ** 6
x = [0 for i in range(maxN + 1)]
i = 2
while i * i <= maxN:
	if not x[i]:
		for j in range(i * i, maxN + 1, i):
			x[j] = 1
	i += 1
prime = [i for i in range(2, maxN + 1) if not x[i]]
(n, m) = mp()
ans = INF
d = defaultdict(int)
l = [li() for i in range(n)]
for i in range(n):
	now = 0
	for j in range(m):
		cur = BS(l[i][j])
		d[i, j] = prime[cur] - l[i][j]
		now += prime[cur] - l[i][j]
	ans = min(ans, now)
for i in range(m):
	now = 0
	for j in range(n):
		now += d[j, i]
	ans = min(ans, now)
pr(ans)


N = 110000
p = list((True for i in range(N)))
Next = list((N for i in range(N)))

def calc():
	p[0] = p[1] = False
	for i in range(2, N):
		if p[i] == True:
			j = i * i
			while j < N:
				p[j] = False
				j += i
	last = N
	for i in range(N - 1, 0, -1):
		if p[i] == True:
			last = i
		Next[i] = last
calc()
(n, m) = map(int, input().split())
a = list((list((0 for j in range(m))) for i in range(n)))
for i in range(n):
	s = list(map(int, input().split()))
	for j in range(m):
		a[i][j] = Next[s[j]] - s[j]
ans = 10 ** 9
for i in range(n):
	sum_row = 0
	for j in range(m):
		sum_row += a[i][j]
	ans = min(ans, sum_row)
for j in range(m):
	sum_col = 0
	for i in range(n):
		sum_col += a[i][j]
	ans = min(ans, sum_col)
print(ans)


def arrayOfPrimes():
	n = 100000
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime

def arrayOfPrimeDistance(primes):
	n = 100000
	distance = 0
	distArray = [0 for i in range(n + 1)]
	distArray[100000] = 3
	for i in range(n - 1, -1, -1):
		if not primes[i]:
			distArray[i] = distArray[i + 1] + 1
	return distArray
primes = arrayOfPrimes()
matrix = []
distanceArray = arrayOfPrimeDistance(primes)
(n, m) = list(map(int, input().split()))
for i in range(n):
	row = list(map(int, input().split()))
	matrix.append(row)
smallerRow = 1000000
smallerCollumn = 1000000
for j in range(n):
	count = 0
	for k in range(m):
		number = matrix[j][k]
		if not primes[number]:
			nextPrime = number + distanceArray[number]
			count += nextPrime - number
	if count < smallerRow:
		smallerRow = count
for x in range(m):
	count = 0
	for y in range(n):
		number = matrix[y][x]
		if not primes[number]:
			nextPrime = number + distanceArray[number]
			count += nextPrime - number
	if count < smallerCollumn:
		smallerCollumn = count
print(smallerRow if smallerRow < smallerCollumn else smallerCollumn)


(rows, cols) = map(int, input().split())
a = []
for i in range(rows):
	a.append([])
	k = list(map(int, input().split()))
	a[i] += k
primes = [True for i in range(100004)]
for num in range(2, 50003):
	for i in range(num + num, 100004, num):
		primes[i] = False
primes[0] = 2
primes[1] = 2
primes[2] = 2
for num in range(3, 100004):
	if primes[num] == True:
		i = num - 1
		while primes[i] == False:
			primes[i] = num
			i -= 1
		primes[num] = num
answer = 300012
for row in range(rows):
	cur = 0
	for col in range(cols):
		cur += primes[a[row][col]] - a[row][col]
	answer = min(answer, cur)
for col in range(cols):
	cur = 0
	for row in range(rows):
		cur += primes[a[row][col]] - a[row][col]
	answer = min(answer, cur)
print(answer)


n = 100100
p = [0, 0] + [1] * n
(p[0], p[1]) = (0, 0)
n1 = int(n ** 0.5)
for i in range(2, n1):
	if p[i] == 1:
		for j in range(i * i, n, i):
			p[j] = 0
for k in range(n, -1, -1):
	if p[k]:
		ind = k
		p[k] = 0
	else:
		p[k] = ind - k
lst = []
(x, y) = map(int, input().split())
for j in range(x):
	l = []
	for i in map(int, input().split()):
		l.append(p[i])
	lst.append(l)
st = []
for x in lst:
	st.append(sum(x))
for x in zip(*lst):
	st.append(sum(x))
print(min(st))


num1 = 100025
num2 = 2
primos = [True] * num1
for i in range(num2, num1):
	j = i
	while j + i < num1:
		j += i
		primos[j] = False
primos[1] = False
primos[0] = False
matriz = []
(n, m) = map(int, input().split())
for i in range(n):
	t = list(map(int, input().split()))
	matriz.append(t)
resposta = 100000

def calcula_linha(res):
	for i in range(n):
		movimentos = 0
		for j in range(m):
			result = matriz[i][j]
			for k in range(result, num1):
				if primos[k] == True:
					movimentos += k - result
					break
		res = min(res, movimentos)
	return res

def calcula_coluna(res):
	for j in range(m):
		movimentos = 0
		for i in range(n):
			result = matriz[i][j]
			for k in range(result, num1):
				if primos[k] == True:
					movimentos += k - result
					break
		res = min(res, movimentos)
	return res
resposta = min(resposta, calcula_linha(resposta))
resposta = min(resposta, calcula_coluna(resposta))
print(resposta)


limit = 300000
primes = [False for x in range(limit)]
columns = [0 for x in range(limit)]
ans = limit
Input = map(int, input().split())
(l, c) = list(Input)

def crivo():
	primes[0] = True
	primes[1] = True
	for i in range(2, limit):
		if not primes[i]:
			for j in range(i + i, limit, i):
				primes[j] = True
	for i in range(limit - 2, -1, -1):
		if primes[i]:
			primes[i] += primes[i + 1]
crivo()
for index in range(0, l):
	rowsAux = map(int, input().split())
	rows = list(rowsAux)
	aux = 0
	for value in range(c):
		aux += primes[rows[value]]
		columns[value] += primes[rows[value]]
	if index == l - 1:
		for value in range(c):
			ans = min(columns[value], ans)
	ans = min(aux, ans)
print(ans)


def f(n):
	m = int(n ** 0.5) + 1
	t = [1, 0] * (n // 2 + 1)
	(t[0], t[1], t[2]) = (1, 1, 0)
	for i in range(3, m):
		if t[i] == 0:
			t[i * i::2 * i] = [1] * ((n - i * i) // (2 * i) + 1)
	for i in range(n - 1, -1, -1):
		if t[i]:
			t[i] = t[i + 1] + 1
	return t
q = f(100007)
(n, m) = list(map(int, input().split()))
t = [[q[j] for j in map(int, input().split())] for i in range(n)]
print(min(min((sum(t[i]) for i in range(n))), min((sum((t[i][j] for i in range(n))) for j in range(m)))))


limite = int(1000000.0)
primos = [True for i in range(limite)]
primos[0] = False
primos[1] = False
for i in range(2, limite):
	if primos[i]:
		for j in range(i ** 2, limite, i):
			primos[j] = False
distancias = [0 for i in range(limite)]
distancias[0] = 2
distancias[1] = 1
base = int(limite // 10 - 1)
while not primos[base]:
	base += 1
for i in range(base, 1, -1):
	if not primos[i]:
		distancias[i] = distancias[i + 1] + 1
entrada = input().split()
n = int(entrada[0])
m = int(entrada[1])
matriz = []
for i in range(n):
	entrada = input().split()
	matriz.append(list(map(int, entrada)))
menor_passo = limite
for i in range(n):
	passos = sum([distancias[matriz[i][j]] for j in range(m)])
	if passos < menor_passo:
		menor_passo = passos
for j in range(m):
	passos = sum([distancias[matriz[i][j]] for i in range(n)])
	if passos < menor_passo:
		menor_passo = passos
print(menor_passo)


matrix_params = input()
params = matrix_params.split(' ')
rows = int(params[0])
cols = int(params[1])
initial_matrix = []
count_r = []
count_c = []
curr_row = []

def is_prime(n):
	if n <= 3:
		return n > 1
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i ** 2 <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i += 6
	return True

def count_to_prime(n):
	count = 0
	while not is_prime(n + count):
		count += 1
	return count
for i in range(cols):
	count_c.append(0)
for i in range(rows):
	count_r.append(0)
	raw_row = input()
	curr_row = raw_row.split(' ')
	initial_matrix.append(curr_row)
for i in range(rows):
	for j in range(cols):
		increase = count_to_prime(int(initial_matrix[i][j]))
		count_c[j] += increase
		count_r[i] += increase

def get_min(array):
	minimum = array[0]
	for i in range(1, len(array)):
		if array[i] < minimum:
			minimum = array[i]
	return minimum
min_cols = get_min(count_c)
min_rows = get_min(count_r)
print(min_cols if min_cols < min_rows else min_rows)


(n, m) = map(int, input().split())
primes = [1 for _ in range(10 ** 6 + 1)]
primes[0] = False
primes[1] = False
for i in range(2, 10 ** 6):
	if primes[i]:
		for j in range(i * i, 10 ** 6, i):
			primes[j] = False
grid = []
for i in range(n):
	grid.append([])
	line = list(map(int, input().split()))
	for nb in line:
		copy = nb
		while primes[nb] ^ 1:
			nb += 1
		grid[i].append(nb - copy)
ans = 10 ** 9
for i in range(n):
	ans = min(ans, sum(grid[i]))
for j in range(m):
	ans = min(ans, sum((grid[i][j] for i in range(n))))
print(ans)


m = 10 ** 5 + 5
cri = [0] * m
pri = []
for i in range(2, m):
	if cri[i] == 0:
		cri[i] = 1
		pri.append(i)
		for j in range(i, m, i):
			cri[j] = 1
dp = [0] * m
for a in range(len(pri) - 1):
	(pa, pb) = (pri[a], pri[a + 1])
	for i in range(pa + 1, pb):
		dp[i] = pb - i
dp[0] = 2
dp[1] = 1
(n, m) = map(int, input().split())
mat = [[dp[int(x)] for x in input().split()] for _ in range(n)]
res = min((sum(col) for col in mat))
for i in range(1, n):
	for j in range(m):
		mat[0][j] += mat[i][j]
print(min(min(mat[0]), res))


import sys
import math
limit = 100025
minhaListadePrimos = [True for i in range(limit + 1)]
primosSeguintestsss = [0 for i in range(200000)]

def crivandu():
	minhaListadePrimos[0] = minhaListadePrimos[1] = False
	for i in range(2, int(math.sqrt(limit))):
		if minhaListadePrimos[i]:
			j = 2
			while i * j <= limit:
				minhaListadePrimos[i * j] = False
				j += 1

def get_primosSeguintestsss():
	for i in range(limit - 1, -1, -1):
		if minhaListadePrimos[i]:
			primosSeguintestsss[i] = 0
		else:
			primosSeguintestsss[i] = 1 + primosSeguintestsss[i + 1]
crivandu()
get_primosSeguintestsss()
dados = input().split(' ')
(n, m) = (int(dados[0]), int(dados[1]))
matrix = []
for i in range(0, n):
	value = input()
	matrix.append(value.split(' '))
best = sys.maxsize
for index_row in range(n):
	best_row = 0
	for index_column in range(m):
		num = int(matrix[index_row][index_column])
		best_row += primosSeguintestsss[num]
	if best_row < best:
		best = best_row
for index_column in range(m):
	best_column = 0
	for index_row in range(n):
		num = int(matrix[index_row][index_column])
		best_column += primosSeguintestsss[num]
	if best_column < best:
		best = best_column
print(best)


(row, column) = map(int, input().split())
matrix = [[*map(int, input().split())] for _ in ' ' * row]
variation = int(100000.0 + 2)
aux = [1, 1] + [0] * variation
for x in range(2, variation):
	aux[x * x::x] = [1] * ((variation - x * x) // x + 1)
for y in range(variation, -1, -1):
	aux[y] *= aux[y + 1] + 1
for i in range(row):
	for j in range(column):
		matrix[i][j] = aux[matrix[i][j]]
collumsSums = min((sum(value) for value in matrix))
rownSums = min((sum(value) for value in zip(*matrix)))
print(min(collumsSums, rownSums))


from bisect import bisect_left

def read():
	return [int(c) for c in input().split()]

def sieve(n=101000):
	ans = [True] * (n + 1)
	ans[0] = False
	ans[1] = False
	for i in range(2, n // 2 + 1):
		if ans[i]:
			mul = 2 * i
			while mul < n + 1:
				ans[mul] = False
				mul += i
	return [i for (i, e) in enumerate(ans) if e]

def main():
	(n, m) = read()
	matrix = [read() for _ in range(n)]
	primes = sieve()
	rows = [0] * n
	cols = [0] * m
	for r in range(n):
		for c in range(m):
			sup_prime = primes[bisect_left(primes, matrix[r][c])]
			cur = sup_prime - matrix[r][c]
			rows[r] += cur
			cols[c] += cur
	print(min(rows + cols))
main()


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from functools import lru_cache
sys.setrecursionlimit(100000000)
int_r = lambda : int(sys.stdin.readline())
str_r = lambda : sys.stdin.readline().strip()
intList_r = lambda : list(map(int, sys.stdin.readline().strip().split()))
strList_r = lambda : list(sys.stdin.readline().strip())
jn = lambda x, l: x.join(map(str, l))
mul = lambda : map(int, sys.stdin.readline().strip().split())
mulf = lambda : map(float, sys.stdin.readline().strip().split())
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
outStr = lambda x: stdout.write(str(x))
mod = 1000000007

def isPrime(n):
	if n <= 1:
		return False
	if n == 2 or n == 3:
		return True
	elif (n - 1) % 6 == 0 or (n + 1) % 6 == 0:
		count = 0
		for i in range(2, ceil(sqrt(n) + 1)):
			if n % i == 0:
				count += 1
				break
		if count == 0:
			return True
		else:
			return False
	else:
		return False

def main():
	(n, m) = intList_r()
	dictt = dict()
	prev = 100003
	for i in range(100000, 0, -1):
		if isPrime(i):
			prev = i
		dictt[i] = prev
	mat = list()
	for i in range(n):
		arr = intList_r()
		mat.append(arr)
	sum_min = 1000000
	for i in range(len(mat)):
		sum = 0
		for j in range(len(mat[0])):
			sum += dictt[mat[i][j]] - mat[i][j]
		sum_min = min(sum, sum_min)
	for j in range(len(mat[0])):
		sum = 0
		for i in range(len(mat)):
			sum += dictt[mat[i][j]] - mat[i][j]
		sum_min = min(sum, sum_min)
	outStr(sum_min)
main()


import math
from sys import stdin

def get_ints():
	return list(map(int, stdin.readline().strip().split()))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(math.sqrt(n) + 1), 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def nextPrime(N):
	if N <= 1:
		return 2
	prime = N
	found = False
	while not found:
		prime = prime + 1
		if isPrime(prime) == True:
			found = True
	return prime
M = 100100
primes = [0] * M
primes[0] = 2
primes[1] = 2
primes[2] = 2
prev = 2
i = 3
primes[i] = 3
while i < M:
	f = i
	if not isPrime(f):
		f = nextPrime(f)
	nextone = nextPrime(f + 1)
	primes[i + 1:nextone] = [nextone] * (nextone - i)
	i += nextone - f
(n, m) = get_ints()
add = [[999] * m for i in range(n)]
for i in range(n):
	line = get_ints()
	for j in range(m):
		add[i][j] = primes[line[j]] - line[j]
minrow = 99999999999
for row in add:
	minrow = min(minrow, sum(row))
mincol = 99999999999
for col in zip(*add):
	mincol = min(mincol, sum(col))
print(min(minrow, mincol))


from sys import stdin, stdout

def INI():
	return int(stdin.readline())

def INL():
	return [int(_) for _ in stdin.readline().split()]

def INS():
	return stdin.readline()

def OPS(ans):
	stdout.write(str(ans) + '\n')

def OPL(ans):
	[stdout.write(str(_) + ' ') for _ in ans]
	stdout.write('\n')

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			yield p
from bisect import bisect_left
(n, m) = INL()
X = []
P = list(SieveOfEratosthenes(1000000))
ans = float('inf')
for _ in range(n):
	U = INL()
	g = []
	for _ in U:
		g.append(P[bisect_left(P, _)] - _)
	X.append(g)
	ans = min(ans, sum(g))
for _ in range(m):
	g = 0
	for __ in range(n):
		g += X[__][_]
	ans = min(ans, g)
print(ans)


(a, b) = map(int, input().split())
c = 100030
f = [0] * c
f[1] = 1
for i in range(2, c):
	if f[i] == 0:
		for j in range(i + i, c, i):
			f[j] = 1
t = 0
for i in range(c - 1, 0, -1):
	if f[i] == 0:
		t = i
	f[i] = t
l = [[int(j) for j in input().split()] for i in range(a)]
for i in range(a):
	for j in range(b):
		t = l[i][j]
		l[i][j] = f[t] - l[i][j]
mx = 10 ** 10
for i in range(a):
	mx = min(mx, sum(l[i]))
for j in range(b):
	t = 0
	for i in range(a):
		t += l[i][j]
	mx = min(mx, t)
print(mx)


import bisect
prime = [0] * 1000001
i = 2
while i * i < 1000001:
	if prime[i] == 0:
		for j in range(i * i, 1000001, i):
			prime[j] = -1
	i += 1
lol = []
for k in range(2, 1000001):
	if prime[k] == 0:
		lol.append(k)
(x, y) = map(int, input().split())
yo = []
lu = []
for i in range(x):
	yo.append([0] * y)
	lu.append(list(map(int, input().split())))
for i in range(x):
	for j in range(y):
		w = bisect.bisect(lol, lu[i][j])
		if lu[i][j] - lol[w - 1] != 0:
			yo[i][j] = abs(lu[i][j] - lol[w])
		else:
			yo[i][j] = 0
z = 1000001
for i in yo:
	z = min(z, sum(i))
for i in range(y):
	s = 0
	for j in range(x):
		s += yo[j][i]
	z = min(s, z)
print(z)


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
from typing import List
sys.setrecursionlimit(99999)
p = []
mx = 10 ** 5 + 1000
f = [0] * mx
for i in range(2, mx):
	if f[i] == 0:
		p.append(i)
		for j in range(i * 2, mx, i):
			f[j] = 1
(n, m) = map(int, input().split())
(row, col) = ([0 for _ in range(n)], [0 for _ in range(m)])
for i in range(n):
	arr = list(map(int, input().split()))
	for j in range(m):
		k = bisect.bisect_left(p, arr[j])
		if p[k] != arr[j]:
			row[i] += p[k] - arr[j]
			col[j] += p[k] - arr[j]
sr = min(row)
sc = min(col)
print(min(sr, sc))


def sieve(n):
	arr = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			arr.append(p)
	return arr
prime = sieve(10 ** 5 + 10 ** 4)
(n, m) = list(map(int, input().split()))
arr = []
cnt = 10 ** 10
for i in range(n):
	arr.append(list(map(int, input().split())))
ind = 0
d = {}
for i in range(1, 101000):
	if i <= prime[ind]:
		d[i] = prime[ind] - i
	else:
		ind += 1
		d[i] = prime[ind] - i
cnt = 10 ** 10
for i in range(n):
	temp = 0
	for j in range(m):
		temp += d[arr[i][j]]
	cnt = min(cnt, temp)
for i in range(m):
	temp = 0
	for j in range(n):
		temp += d[arr[j][i]]
	cnt = min(cnt, temp)
print(cnt)


import sys, threading, os.path
import collections, heapq, math, bisect
import string
from platform import python_version
import itertools
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)

def generate_primes(n):
	res = []
	isPrime = [True] * (n * 5)
	(isPrime[0], isPrime[1]) = (0, 0)
	for i in range(2, n + 1):
		if i * i > n + 1:
			break
		if isPrime[i]:
			for j in range(i * 2, n + 1, i):
				isPrime[j] = 0
	res.append(2)
	for i in range(3, n + 1, 2):
		if isPrime[i]:
			res.append(i)
	return res

def main():
	if os.path.exists('input.txt'):
		input = open('input.txt', 'r')
	else:
		input = sys.stdin
	(n, m) = list(map(int, input.readline().split()))
	mat = []
	for i in range(n):
		mat.append(list(map(int, input.readline().split())))
	allprimes = generate_primes(150000)
	tostore = []
	for i in range(n):
		tostore.append([])
		for j in range(m):
			x = bisect.bisect(allprimes, mat[i][j])
			if allprimes[x - 1] == mat[i][j]:
				tostore[i].append(0)
			else:
				tostore[i].append(abs(mat[i][j] - allprimes[x]))
	(rowsum, colsum) = ([0] * 501, [0] * 501)
	for i in range(n):
		for j in range(m):
			rowsum[i] += tostore[i][j]
			colsum[j] += tostore[i][j]
	minone = min(min(rowsum[:n]), min(colsum[:m]))
	output = minone
	if os.path.exists('output.txt'):
		open('output.txt', 'w').writelines(str(output))
	else:
		sys.stdout.write(str(output))
main()


primes = []
isPrime = [True for i in range(10 ** 5 + 7)]
nextPrime = []
isPrime[1] = isPrime[0] = False
for i in range(2, 10 ** 5 + 7):
	if isPrime[i] == True:
		primes.append(i)
		for j in range(i * i, 10 ** 5 + 7, i):
			isPrime[j] = False
aux = 0
for i in range(10 ** 5 + 1):
	nextPrime.append(primes[aux])
	if isPrime[i] == True:
		aux += 1
(n, m) = list(map(int, input().split(' ')))
matriz = [list(map(int, input().split(' '))) for i in range(n)]
answer = float('inf')
for i in range(n):
	possibleAnswer = 0
	for j in range(m):
		possibleAnswer += nextPrime[matriz[i][j]] - matriz[i][j]
	answer = min(answer, possibleAnswer)
for i in range(m):
	possibleAnswer = 0
	for j in range(n):
		possibleAnswer += nextPrime[matriz[j][i]] - matriz[j][i]
	answer = min(answer, possibleAnswer)
print(answer)


def _min(x, y):
	if x < y:
		return x
	if y <= x:
		return y
n = 100100
prime = [True for i in range(n + 1)]
(prime[0], prime[1]) = (False, False)
p = 2
while p * p <= n:
	if prime[p] == True:
		for i in range(p * p, n + 1, p):
			prime[i] = False
	p += 1
n = 100100
nextPrime = [0 for _ in range(n + 1)]
currentPrime = -1
for i in range(n, -1, -1):
	if prime[i]:
		nextPrime[i] = i
		currentPrime = i
	elif currentPrime == -1:
		nextPrime[i] = -1
	else:
		nextPrime[i] = currentPrime
(n, m) = map(int, input().split())
rows = [0 for i in range(n)]
cols = [0 for i in range(m)]
for r in range(n):
	row = [int(x) for x in input().split()]
	for c in range(m):
		x = row[c]
		if not prime[x]:
			x = nextPrime[x]
		rows[r] += x - row[c]
		cols[c] += x - row[c]
min_row = min(rows)
min_cols = min(cols)
print(_min(min_row, min_cols))


def get_input_matrix():
	user_input = input().split()
	n = int(user_input[0])
	m = int(user_input[1])
	matrix = []
	for i in range(n):
		user_input_matrix = input().split()
		row = []
		for j in range(m):
			row.append(int(user_input_matrix[j]))
		matrix.append(row)
	return (matrix, n, m)

def prime_sieve(n):
	(primes, sieve) = ({}, [True] * int(n + 1))
	for p in range(2, n + 1):
		if sieve[p]:
			primes[p] = p
			for i in range(p * p, n + 1, p):
				sieve[i] = False
	return primes
(matrix, n, m) = get_input_matrix()
primes = prime_sieve(100100)
lesser_row_count = 999999
columns_count = [0] * m
for i in range(n):
	row_count = 0
	for j in range(m):
		while not primes.get(matrix[i][j]):
			matrix[i][j] += 1
			row_count += 1
			columns_count[j] += 1
			if row_count >= lesser_row_count and columns_count[j] >= lesser_row_count:
				break
	lesser_row_count = min(row_count, lesser_row_count)
print(min(lesser_row_count, *columns_count))


import math

def remove_zeros(listNum):
	listNumAux = []
	for num in listNum:
		if num != 0:
			listNumAux.append(num)
	return listNumAux

def sieve_of_eratosthenes():
	limNumbers = 100004
	limTest = math.ceil(math.sqrt(limNumbers))
	listNum = list(range(2, limNumbers))
	i = 0
	for i in range(0, limTest):
		if listNum[i] != 0:
			for j in range(listNum[i] ** 2 - 2, limNumbers - 2, listNum[i]):
				listNum[j] = 0
	listNum = remove_zeros(listNum)
	return listNum

def bs(A, esquerda, direita, item):
	if direita < esquerda or len(A) == 2:
		if A[esquerda] > item:
			return A[esquerda]
		else:
			return A[direita]
	meio = (esquerda + direita) // 2
	if A[meio] == item:
		return A[meio]
	elif A[meio] > item:
		return bs(A, esquerda, meio - 1, item)
	else:
		return bs(A, meio + 1, direita, item)

def main():
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	primeNumbers = sieve_of_eratosthenes()
	sumCols = [0 for x in range(m)]
	minLine = 1000000
	for i in range(n):
		line = input().split(' ')
		sumLine = 0
		for j in range(m):
			num = int(line[j])
			dist = bs(primeNumbers, 0, len(primeNumbers), num) - num
			sumLine += dist
			sumCols[j] += dist
		if minLine > sumLine:
			minLine = sumLine
	minCol = 1000000
	for sumCol in sumCols:
		if minCol > sumCol:
			minCol = sumCol
	if minCol < minLine:
		print(minCol)
	else:
		print(minLine)
main()


def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def MAP2():
	return map(float, input().split())

def LIST():
	return list(map(int, input().split()))

def STRING():
	return input()
import string
import sys
from heapq import heappop, heappush
from bisect import *
from collections import deque, Counter, defaultdict
from math import *
from itertools import permutations, accumulate
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def find_primes(n):
	primes = [True] * (n + 1)
	primes[0] = primes[1] = False
	p = 2
	while p * p <= n:
		i = p + p
		while i <= n:
			primes[i] = False
			i += p
		p += 1
	l = []
	for i in range(2, n + 1):
		if primes[i]:
			l.append(i)
	return l

def cols(n, m, g):
	l = []
	for i in range(m):
		t = []
		for j in range(n):
			t.append(g[j][i])
		l.append(t)
	return l

def near_prime(l, x):
	y = bisect_left(l, x)
	return l[y]
l = find_primes(10 ** 5 + 10)
(n, m) = MAP()
g = []
for i in range(n):
	g.append(LIST())
res2 = []
for i in range(n):
	c = 0
	for j in range(m):
		k = near_prime(l, g[i][j])
		c += k - g[i][j]
	res2.append(c)
l2 = cols(n, m, g)
res1 = []
for i in l2:
	c = 0
	for j in i:
		k = near_prime(l, j)
		c += k - j
	res1.append(c)
r1 = min(res2)
r2 = min(res1)
print(min(r1, r2))


def sieve(num):
	primes = [0] * (num + 1)
	prime_flag = [True] * (num + 1)
	prime_flag[0] = prime_flag[1] = False
	i = 2
	while i * i <= num:
		if prime_flag[i]:
			for j in range(i * i, num + 1, i):
				prime_flag[j] = False
		i += 1
	for i in range(num - 1, -1, -1):
		if not prime_flag[i]:
			primes[i] = 1 + primes[i + 1]
	return primes
(m, n) = map(int, input().split())
matrix = []
max_number = 100020
prime_array = sieve(max_number)
line_sum = max_number
colum_sum = [0] * n
for i in range(m):
	line = list(map(int, input().split()))
	matrix.append(line)
	aux_line = 0
	for j in range(n):
		diff_of_position = prime_array[matrix[i][j]]
		aux_line += diff_of_position
		colum_sum[j] += diff_of_position
	if aux_line < line_sum:
		line_sum = aux_line
min_value = line_sum
for i in colum_sum:
	if i < min_value:
		min_value = i
print(min_value)


(n, m) = map(int, input().split())
maximum = 10 ** 5 + 3
prime = [True] * (maximum + 1)
(prime[0], prime[1]) = (False, False)
for i in range(2, maximum + 1):
	if prime[i]:
		for j in range(i + i, maximum + 1, i):
			prime[j] = False
matrix = []
sums = [[0] * n, [0] * m]
ans = 1000000000.0 + 7
for i in range(n):
	row = [int(i) for i in input().split()]
	new_row = []
	for j in range(m):
		num = row[j]
		add = 0
		while num <= maximum and (not prime[num]):
			add += 1
			num += 1
		new_row.append(add)
		sums[0][i] += add
		sums[1][j] += add
	matrix.append(new_row)
	ans = min(ans, sums[0][i])
for i in range(m):
	ans = min(ans, sums[1][i])
print(ans)


limite = 100000
crivo = [True] * (limite + 1)
crivo[0] = False
crivo[1] = False
i = 2
while i * i <= limite:
	if crivo[i] == True:
		for j in range(i * 2, limite + 1, i):
			crivo[j] = False
	i += 1
crivo[100000] = 100003
for i in range(99999, -1, -1):
	if not crivo[i]:
		if type(crivo[i + 1]) == int:
			crivo[i] = crivo[i + 1]
		else:
			crivo[i] = i + 1
(l, c) = map(int, input().split())
matriz = []
for i in range(l):
	matriz.append(list(map(int, input().split())))
linhas = [0] * l
colunas = [0] * c
for i in range(l):
	for j in range(c):
		d = crivo[matriz[i][j]]
		if type(d) != int:
			linhas[i] += 0
			colunas[j] += 0
		else:
			linhas[i] += d - matriz[i][j]
			colunas[j] += d - matriz[i][j]
print(min(min(linhas), min(colunas)))


def genSieve():
	n = 200000
	isPrime = [True for i in range(n)]
	isPrime[0] = isPrime[1] = False
	for i in range(2, n):
		j = i
		while i * j < n:
			isPrime[i * j] = False
			j += 1
	return isPrime
isPrime = genSieve()

def distToPrime(n):
	dist = 0
	while True:
		if isPrime[n + dist]:
			break
		dist += 1
	return dist

def toDistMatrix(matrix):
	(n, m) = (len(matrix), len(matrix[0]))
	for i in range(n):
		for j in range(m):
			matrix[i][j] = distToPrime(matrix[i][j])

def getAns(matrix):
	(n, m) = (len(matrix), len(matrix[0]))
	ans = 1000000
	for i in range(n):
		temp = 0
		for j in range(m):
			temp += matrix[i][j]
		ans = min(temp, ans)
	for j in range(m):
		temp = 0
		for i in range(n):
			temp += matrix[i][j]
		ans = min(temp, ans)
	return ans
(n, m) = (int(x) for x in input().split())
matrix = [[int(x) for x in input().split()] for x in range(n)]
toDistMatrix(matrix)
print(getAns(matrix))


import os
import sys
from io import BytesIO, IOBase
from bisect import bisect_left as bl
from bisect import bisect_right as br
primes = [2]
import math

def getprime():
	global primes
	for x in range(2, 111111):
		chk = 0
		for y in range(2, math.floor(math.sqrt(x)) + 2):
			if x % y == 0:
				chk = 1
				break
		if chk == 0:
			primes.append(x)

def main():
	getprime()
	global primes
	(n, m) = map(int, input().split(' '))
	a = [list(map(int, input().split(' '))) for x in range(n)]
	ans = int(1e+19)
	for x in range(n):
		cnt = 0
		for y in range(m):
			cnt += primes[bl(primes, a[x][y])] - a[x][y]
		ans = min(ans, cnt)
	for x in range(m):
		temp = []
		for y in range(n):
			temp.append(a[y][x])
		cnt = 0
		for x in temp:
			cnt += primes[bl(primes, x)] - x
		ans = min(ans, cnt)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(math.sqrt(n) + 1), 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def nextPrime(N):
	if N <= 1:
		return 2
	prime = N
	found = False
	while not found:
		prime = prime + 1
		if isPrime(prime) == True:
			found = True
	return prime

def nextPrimeList(n):
	arr = [False] * (n + 1)
	for i in range(2, n + 1):
		if not arr[i]:
			j = 2
			while j * i <= n:
				arr[j * i] = True
				j += 1
	res = [2] * (n + 1)
	i = 2
	while i <= n:
		if not arr[i]:
			res[i] = i
		else:
			j = i
			while j <= n and arr[j] == True:
				j += 1
			if j > n:
				nxt = nextPrime(j - 1)
				res[i] = nxt
			else:
				res[i] = j
		i += 1
	return res

def solve(matrix, n, m):
	maxim = matrix[0][0]
	for i in range(n):
		for j in range(m):
			maxim = max(maxim, matrix[i][j])
	nxtPList = nextPrimeList(maxim)
	scores = [[0 for _ in range(m)] for _ in range(n)]
	for i in range(n):
		for j in range(m):
			scores[i][j] = nxtPList[matrix[i][j]] - matrix[i][j]
	res = math.inf
	for i in range(n):
		rowScore = 0
		for j in range(m):
			rowScore += scores[i][j]
		res = min(res, rowScore)
	for i in range(m):
		coloumnScore = 0
		for j in range(n):
			coloumnScore += scores[j][i]
		res = min(res, coloumnScore)
	return res
(n, m) = map(int, input().split())
matrix = []
for _ in range(n):
	row = list(map(int, input().split()))
	matrix.append(row)
print(solve(matrix, n, m))


import sys
input = lambda : sys.stdin.readline().strip('\r\n')

def sieve(n):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
(n, m) = map(int, input().split())
no = 10 ** 5 + 100
prime = [True for i in range(no + 1)]
sieve(no)
prime[0] = False
prime[1] = False
req = [0] * no
for i in range(no - 2, -1, -1):
	if prime[i]:
		req[i] = 0
	else:
		req[i] = req[i + 1] + 1
mat = []
for i in range(n):
	b = list(map(int, input().split()))
	mat.append(b)
ans = float('inf')
for i in range(n):
	temp = 0
	for j in range(m):
		temp += req[mat[i][j]]
	ans = min(ans, temp)
for i in range(m):
	temp = 0
	for j in range(n):
		temp += req[mat[j][i]]
	ans = min(ans, temp)
print(ans)


def sieve(n):
	prime = [False, False] + [True] * (n - 1)
	i = 2
	while i * i <= n:
		if prime[i]:
			for j in range(i * i, n + 1, i):
				prime[j] = False
		i += 1
	return [i for i in range(n + 1) if prime[i]]

def binarySearch(v):
	n = len(p)
	(left, right) = (-1, n)
	while left + 1 < right:
		mid = left + right >> 1
		if p[mid] < v:
			left = mid
		else:
			right = mid
	return p[right] - v
(sizeI, sizeJ) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(sizeI)]
p = sieve(10 ** 5 + 100)
cost = [[None for _ in range(sizeJ)] for _ in range(sizeI)]
for i in range(sizeI):
	for j in range(sizeJ):
		cost[i][j] = binarySearch(a[i][j])
rows = [sum(r) for r in cost]
cols = [sum(r) for r in zip(*cost)]
print(min(min(rows), min(cols)))


def get_primes():
	prime = [True] * 100100
	prime[0] = False
	prime[1] = False
	prime[2] = True
	n = 2
	while n < len(prime):
		i = n + n
		while prime[n] and i < len(prime):
			prime[i] = False
			i += n
		n += 1
	return prime
primes = get_primes()
(n, m) = map(int, input().split())
diffs = [[-1 for j in range(m)] for i in range(n)]
min_row = -1
for i in range(n):
	row = 0
	els = list(map(int, input().split()))
	for j in range(m):
		el = els[j]
		k = el
		while not primes[k]:
			k += 1
		diffs[i][j] = k - el
		row += diffs[i][j]
	if min_row == -1:
		min_row = row
	else:
		min_row = min(min_row, row)
min_col = -1
for j in range(m):
	col = 0
	for i in range(n):
		col += diffs[i][j]
	if min_col == -1:
		min_col = col
	else:
		min_col = min(min_col, col)
print(min(min_row, min_col))


(num_rows, num_columns) = map(int, input().split())
limit = int(100000.0 + 2)
diffs = [2, 1, 0, 0] + [1, 0] * ((limit - 2) // 2)
for i in range(3, limit):
	if not diffs[i]:
		diffs[i * i::i] = [1] * ((limit - i * i) // i + 1)
for i in range(limit, 4, -1):
	diffs[i] *= diffs[i + 1] + 1
matrix_diffs = [[diffs[j] for j in map(int, input().split())] for i in range(num_rows)]
min_moves_to_rows = min((sum(i) for i in matrix_diffs))
min_moves_to_cols = min((sum(i) for i in zip(*matrix_diffs)))
print(min(min_moves_to_rows, min_moves_to_cols))


import os
import sys
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def seive(n):
	primes = [True] * (n + 1)
	ans = []
	for i in range(2, n):
		if not primes[i]:
			continue
		j = 2 * i
		while j <= n:
			primes[j] = False
			j += i
	for p in range(2, n + 1):
		if primes[p]:
			ans += [p]
	return ans

def factors(n):
	factors = []
	x = 2
	while x * x <= n:
		while n % x == 0:
			factors.append(x)
			n //= x
		if n > 1:
			factors.append(x)
	return factors

def main():
	try:
		primes = seive(1000000)
		from bisect import bisect_left
		(n, m) = invr()
		a = []
		c = [0] * (n + m)
		for i in range(n):
			a.append(inlt())
		for i in range(n):
			for j in range(m):
				val = bisect_left(primes, a[i][j])
				if primes[val] != a[i][j]:
					c[i] += primes[val] - a[i][j]
					c[n + j] += primes[val] - a[i][j]
		print(min(c))
	except Exception as e:
		print(e)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def Bin(li, x):
	i = 0
	j = len(li) - 1
	while i < j:
		m = int((i + j) / 2)
		if x > li[m]:
			i = m + 1
		else:
			j = m
	return j

def intpolsearch(values, x):
	idx0 = 0
	idxn = len(values) - 1
	while idx0 <= idxn and x >= values[idx0] and (x <= values[idxn]):
		mid = idx0 + int(float(idxn - idx0) / (values[idxn] - values[idx0]) * (x - values[idx0]))
		if values[mid] < x and values[mid + 1] > x or values[mid] == x:
			return mid + 1
		if values[mid] < x:
			idx0 = mid + 1

def G():
	n = 105000
	a = [i for i in range(n + 1)]
	a[0] = 0
	lst = []
	i = 2
	while i <= n:
		if a[i] != 0:
			lst.append(a[i])
		for j in range(i, n + 1, i):
			a[j] = 0
		i += 1
	data = input().split()
	(n, m) = (int(data[0]), int(data[1]))
	matrix = []
	sum_j = [0 for i in range(m)]
	summ = 999999999999
	for i in range(n):
		s = input().split()
		now = []
		for j in range(m):
			if int(s[j]) == 1:
				el = 1
			else:
				k = Bin(lst, int(s[j]))
				el = lst[k] - int(s[j])
			now.append(el)
			sum_j[j] += el
		matrix.append(now)
		ns = sum(now)
		if ns < summ:
			summ = ns
	min_j = min(sum_j)
	if min_j < summ:
		print(min_j)
	else:
		print(summ)
G()


import math

def prime(n):
	ok = True
	for i in range(2, int(math.sqrt(n))):
		if n % i == 0:
			ok = False
			break
	if ok:
		return True
	else:
		return False

def fact(a, b):
	ans = 1
	for i in range(a, b + 1):
		ans *= i
	return str(ans) - 1

def comb(n, c):
	return fact(n) // (fact(n - c) * c)

def primesieve(x):
	nos = [1 for i in range(x + 1)]
	(nos[0], nos[1]) = (0, 0)
	p = 2
	while p <= x:
		if nos[p]:
			for i in range(p * 2, x + 1, p):
				nos[i] = 0
		p += 1
	ans = []
	for i in range(x + 1):
		if nos[i]:
			ans.append(i)
	return ans

def srh(grid, x):
	left = 0
	right = len(grid)
	while left < right:
		mid = (left + right) // 2
		if grid[mid] > x:
			right = mid
		else:
			left = mid + 1
	if grid[left - 1] == x:
		return grid[left - 1]
	if left == len(grid):
		return grid[left - 1]
	return grid[left]
ps = primesieve(100200)
(n, m) = map(int, input().split())
grid = []
for i in range(n):
	grid.append(list(map(int, input().split())))
ptgrid = [[0 for i in range(m)] for i in range(n)]
for f in range(n):
	for s in range(m):
		ptgrid[f][s] = srh(ps, grid[f][s]) - grid[f][s]
ans = int(1000000.0)
for s in range(m):
	tans = 0
	for f in range(n):
		tans += ptgrid[f][s]
	ans = min(ans, tans)
for i in range(n):
	ans = min(ans, sum(ptgrid[i]))
print(ans)


import sys

class MyReader:

	def __init__(self):
		filename = 'file.in'
		if self.isLocal():
			self.file = open(filename)
		self.str = ['']
		self.ind = 1

	def isLocal(self):
		return len(sys.argv) > 1 and sys.argv[1] == 'SCHULLZ'

	def nextString(self):
		if self.isLocal():
			return self.file.read()
		else:
			return input()

	def nextInt(self):
		return int(self.nextToken())

	def nextToken(self):
		if self.ind >= len(self.str):
			self.ind = 0
			self.str = self.nextString().split()
		self.ind += 1
		return self.str[self.ind - 1]
rdr = MyReader()
n = rdr.nextInt()
m = rdr.nextInt()
a = [[0 for x in range(m)] for y in range(n)]
for i in range(0, n):
	for j in range(0, m):
		a[i][j] = rdr.nextInt()
was = []
MX = 200500
for i in range(0, MX):
	was.append(False)
for i in range(2, MX):
	if was[i] == False:
		for j in range(i + i, MX, i):
			was[j] = True
was[1] = True
was[0] = True
nxt = []
for i in range(0, MX):
	nxt.append(-1)
prev = -1
for i in range(MX - 1, -1, -1):
	if was[i] == False:
		prev = i
	nxt[i] = prev
res = MX * 505
for i in range(0, n):
	tres = 0
	for j in range(0, m):
		tres += nxt[a[i][j]] - a[i][j]
	res = min(res, tres)
for j in range(0, m):
	tres = 0
	for i in range(0, n):
		tres += nxt[a[i][j]] - a[i][j]
	res = min(res, tres)
assert res != MX * 505
print(res)


import math, bisect
from collections import Counter, defaultdict
I = lambda : int(input())
M = lambda : map(int, input().split())
LI = lambda : list(map(int, input().split()))
(n, m) = M()
a = []
for i in range(n):
	b = LI()
	a += [b]
prime = [1] * (10 ** 6 + 1)
i = 2
while i * i <= 10 ** 6:
	if prime[i]:
		for j in range(i + i, 10 ** 6 + 1, i):
			prime[j] = 0
	i += 1
ans = []
for i in range(2, 10 ** 6 + 1):
	if prime[i]:
		ans += [i]
mi = 10000000
for i in range(n):
	c = 0
	for j in range(m):
		d = bisect.bisect_left(ans, a[i][j])
		c += abs(ans[d] - a[i][j])
	mi = min(mi, c)
for j in range(m):
	c = 0
	for i in range(n):
		d = bisect.bisect_left(ans, a[i][j])
		c += abs(ans[d] - a[i][j])
	mi = min(mi, c)
print(mi)


from bisect import bisect_left

def genprimes(limit):
	lim = limit // 6
	sieve = [False, True, True] * lim
	lim = lim * 3 - 1
	for (i, s) in enumerate(sieve):
		if s:
			(p, pp) = (i * 2 + 3, (i + 3) * i * 2 + 3)
			le = (lim - pp) // p + 1
			if le > 0:
				sieve[pp::p] = [False] * le
			else:
				break
	sieve[0] = sieve[3] = True
	res = [i * 2 + 3 for (i, f) in enumerate(sieve) if f]
	res[:4] = [2, 3, 5, 7]
	return res

def main():
	primes = genprimes(100004)
	(n, m) = map(int, input().split())
	res = [0] * m
	for y in range(n):
		rw = 0
		for (x, z) in enumerate(map(int, input().split())):
			p = primes[bisect_left(primes, z)] - z
			res[x] += p
			rw += p
		res.append(rw)
	print(min(res))
main()


def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def MAP2():
	return map(float, input().split())

def LIST():
	return list(map(int, input().split()))

def STRING():
	return input()
import string
import sys
from heapq import heappop, heappush
from bisect import *
from collections import deque, Counter, defaultdict
from math import *
from itertools import permutations, accumulate
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def solve(n):
	prime = [True for i in range(n + 1)]
	prime[0] = prime[1] = False
	p = 2
	while p * p <= n:
		if prime[p]:
			i = p * p
			while i <= n:
				prime[i] = False
				i += p
		p += 1
	d = []
	for i in range(2, n + 1):
		if prime[i]:
			d.append(i)
	return d

def search(arr, l, r, x):
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return arr[mid]
		elif arr[mid] > x:
			r = mid - 1
		else:
			l = mid + 1
	return arr[l]
(n, m) = MAP()
g = []
for i in range(n):
	g.append(LIST())
p = solve(10 ** 5 + 9)
rows = []
for i in range(n):
	c = 0
	for j in range(m):
		x = search(p, 0, len(p), g[i][j])
		c += x - g[i][j]
	rows.append(c)
cols = []
for i in range(m):
	c = 0
	for j in range(n):
		x = search(p, 0, len(p), g[j][i])
		c += x - g[j][i]
	cols.append(c)
r1 = 1000000000
r2 = 1000000000
if len(rows) > 0:
	r1 = min(rows)
if len(cols) > 0:
	r2 = min(cols)
r3 = min(r1, r2)
print(r3)


number = 102001
numberD = 2
prime = [1] * number
prime[1] = 0
prime[0] = 0
for i in range(numberD, number):
	j = i
	while j + i < number:
		j += i
		prime[j] = 0
l = []
(n, m) = map(int, input().split())
for i in range(n):
	t = list(map(int, input().split()))
	l.append(t)
ans = 60000000
for i in range(n):
	tot = 0
	for j in range(m):
		result = l[i][j]
		for k in range(result, number):
			if prime[k] == 1:
				tot += k - result
				break
	ans = min(ans, tot)
for j in range(m):
	tot = 0
	for i in range(n):
		result = l[i][j]
		for k in range(result, number):
			if prime[k] == 1:
				tot += k - result
				break
	ans = min(ans, tot)
print(ans)


n = 10 ** 5 + 4
arr = [True for i in range(n)]
(arr[0], arr[1]) = (False, False)
for i in range(2, n):
	if arr[i] == True:
		curr = i
		while i * curr < n:
			arr[i * curr] = False
			curr += 1
for i in range(10 ** 5 + 3, -1, -1):
	if arr[i] == True:
		curr = i
	arr[i] = curr - i
(n, m) = [int(x) for x in input().split()]
ans = 100000000000
a = []
for i in range(n):
	a.append([int(x) for x in input().split()])
for i in range(n):
	curr = 0
	for j in range(m):
		curr += arr[a[i][j]]
	ans = min(ans, curr)
for i in range(m):
	curr = 0
	for j in range(n):
		curr += arr[a[j][i]]
	ans = min(ans, curr)
print(ans)


max = 150035
primes = [0 for x in range(max)]

def generatePrimes():
	primes[1] = primes[0] = 1
	for i in range(2, max):
		if primes[i] == 0:
			for j in range(i + i, max, i):
				primes[j] = 1
	for i in range(max - 2, -1, -1):
		if primes[i] != 0:
			primes[i] += primes[i + 1]
generatePrimes()
columns = [0 for x in range(max)]
(n, m) = map(int, input().split())
res = 10 ** 9
for i in range(0, n):
	aux = 0
	query = list(map(int, input().split()))
	for j in range(m):
		aux += primes[query[j]]
		columns[j] += primes[query[j]]
	if i == n - 1:
		for j in range(m):
			res = min(columns[j], res)
	res = min(aux, res)
print(res)


nearest_prime = [0] * int(100000.0 + 1)
nearest_prime[0] = 2
nearest_prime[1] = 1
prime_bool = [0] * int(100000.0 + 1)

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
a = []
for i in range(2, int(100000.0) + 1):
	if is_prime(i):
		a.append(i)
		prime_bool[i] = 1
for i in range(100001, 1000001):
	if is_prime(i):
		a.append(i)
		break
np = a[-1]
for i in range(int(100000.0), 1, -1):
	if prime_bool[i]:
		nearest_prime[i] = 0
		np = i
	else:
		nearest_prime[i] = np - i
ans = 1000000000.0
(n, m) = list(map(int, input().split()))
arr = []
for i in range(n):
	arr.append(list(map(int, input().split())))
for i in range(n):
	req = 0
	for j in range(m):
		req += nearest_prime[arr[i][j]]
	ans = min(ans, req)
for i in range(m):
	req = 0
	for j in range(n):
		req += nearest_prime[arr[j][i]]
	ans = min(ans, req)
print(ans)


(n, m) = map(int, input().split())
matrix = [[*map(int, input().split())] for _ in range(n)]
MAX_ELEM = int(200000.0)

def sieve():
	prime = [1] * MAX_ELEM
	i = 2
	while i * i < MAX_ELEM:
		if prime[i]:
			j = 2
			while i * j < MAX_ELEM:
				prime[i * j] = False
				j += 1
		i += 1
	prime[0] = prime[1] = False
	nxtPrime = [0] * MAX_ELEM
	cur = -1
	for i in range(MAX_ELEM - 1, -1, -1):
		if prime[i]:
			cur = i
		nxtPrime[i] = cur
	return nxtPrime
nxtPrime = sieve()
ans = int(1000000000.0)
for i in range(n):
	res = 0
	for k in range(m):
		res += nxtPrime[matrix[i][k]] - matrix[i][k]
	ans = min(ans, res)
for j in range(m):
	res = 0
	for k in range(n):
		res += nxtPrime[matrix[k][j]] - matrix[k][j]
	ans = min(ans, res)
print(ans)


def to_prime(n):
	step = 0
	i = n
	while not is_prime[i]:
		step += 1
		i += 1
	return step
R = 10 ** 5 + 300
is_prime = [0] * (R + 1)
is_prime[1] = 1
d = 2
while d * d <= R:
	if not is_prime[d]:
		for i in range(d ** 2, R + 1, d):
			is_prime[i] = 1
	d += 1
for i in range(R + 1):
	if is_prime[i]:
		k = i
		step = 0
		while k <= R and is_prime[k]:
			k += 1
			step += 1
		is_prime[i] = step
(n, m) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
min_step = 10 ** 5
for j in range(n):
	step = 0
	i = 0
	while i < m:
		if is_prime[a[j][i]] > 0:
			step += is_prime[a[j][i]]
		i += 1
	if step < min_step:
		min_step = step
for j in range(m):
	step = 0
	i = 0
	while i < n:
		if is_prime[a[i][j]] > 0:
			step += is_prime[a[i][j]]
		i += 1
	if step < min_step:
		min_step = step
print(min_step)


m = 1000000
p = 2
d = [-1] * m
while p ** 2 <= m:
	if d[p] == -1:
		for i in range(p * 2, m, p):
			d[i] = 0
	p += 1
d[0] = 0
d[1] = 0
w = []
g = 0
for j in range(m - 1, 1, -1):
	if d[j] != -1:
		w.append(g)
	else:
		g = j
		w.append(g)
w.append(2)
w.append(2)
sq = w[::-1]
(n, m) = map(int, input().split())
t = []
f = []
for i in range(n):
	s = list(map(int, input().split()))
	t.append(s)
for i in range(m):
	h = []
	for j in range(n):
		h.append(t[j][i])
	f.append(h)
ans = 999999999
for i in range(n):
	u = 0
	for j in range(m):
		u += sq[t[i][j]] - t[i][j]
	ans = min(u, ans)
for i in range(m):
	u = 0
	for j in range(n):
		u += sq[f[i][j]] - f[i][j]
	ans = min(u, ans)
print(ans)


k = [0] * 200001
primes = []
for i in range(2, 200001):
	if k[i] == 0:
		primes.append(i)
		for j in range(i, 200001, i):
			k[j] = 1

def bin(x):
	(lo, hi) = (0, len(primes))
	ans = 0
	while lo <= hi:
		mid = (hi + lo) // 2
		if primes[mid] == x:
			return 0
		if primes[mid] < x:
			lo = mid + 1
		else:
			ans = mid
			hi = mid - 1
	return primes[ans] - x
(a, b) = map(int, input().split())
r = [0] * a
c = [0] * b
for i in range(a):
	gh = 0
	for (u, v) in enumerate(map(int, input().split())):
		t = bin(v)
		c[u] += t
		gh += t
	r[i] = gh
print(min(min(r), min(c)))


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def seive():
	prime = [1 for i in range(10 ** 6 + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(10 ** 6 + 1):
		if prime[i]:
			for j in range(2 * i, 10 ** 6 + 1, i):
				prime[j] = 0
	return prime
(n, m) = L()
A = [L() for i in range(n)]
p = seive()
P = []
for i in range(2, 10 ** 6 + 1):
	if p[i] == 1:
		P.append(i)
r = {}
c = {}
rmax = cmax = 0
for i in range(n):
	for j in range(m):
		idx = bl(P, A[i][j])
		nxt = P[idx]
		r[i] = r.get(i, 0) + nxt - A[i][j]
		c[j] = c.get(j, 0) + nxt - A[i][j]
ans = 10 ** 20
for ele in r:
	ans = min(ans, r[ele])
for ele in c:
	ans = min(ans, c[ele])
print(ans)
endtime = time.time()


from sys import stdin, stdout
input = stdin.readline
import math, bisect
prime = [1] * 102001
prime[1] = 0
prime[0] = 0
for i in range(2, 102001):
	j = i
	while j + i < 102001:
		j += i
		prime[j] = 0
l = []
(n, m) = map(int, input().split())
for i in range(n):
	t = list(map(int, input().split()))
	l.append(t)
ans = 50000000
for i in range(n):
	tot = 0
	for j in range(m):
		ele = l[i][j]
		for k in range(ele, 102001):
			if prime[k] == 1:
				tot += k - ele
				break
	ans = min(ans, tot)
for j in range(m):
	tot = 0
	for i in range(n):
		ele = l[i][j]
		for k in range(ele, 102001):
			if prime[k] == 1:
				tot += k - ele
				break
	ans = min(ans, tot)
print(ans)


import sys
import math
limit = 100025
list_primes = [True for i in range(limit + 1)]
next_primes = [0 for i in range(200000)]

def SieveOfEratosthenes():
	list_primes[0] = list_primes[1] = False
	for i in range(2, int(math.sqrt(limit))):
		if list_primes[i]:
			j = 2
			while i * j <= limit:
				list_primes[i * j] = False
				j += 1

def get_next_primes():
	for i in range(limit - 1, -1, -1):
		if list_primes[i]:
			next_primes[i] = 0
		else:
			next_primes[i] = 1 + next_primes[i + 1]
SieveOfEratosthenes()
get_next_primes()
dados = input().split(' ')
(n, m) = (int(dados[0]), int(dados[1]))
matrix = []
for i in range(0, n):
	value = input()
	matrix.append(value.split(' '))
best = sys.maxsize
for index_row in range(n):
	best_row = 0
	for index_column in range(m):
		num = int(matrix[index_row][index_column])
		best_row += next_primes[num]
	if best_row < best:
		best = best_row
for index_column in range(m):
	best_column = 0
	for index_row in range(n):
		num = int(matrix[index_row][index_column])
		best_column += next_primes[num]
	if best_column < best:
		best = best_column
print(best)


def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return [str(x) for x in stdin.readline().split()]

def count_prime(n):
	prim = defaultdict(lambda : 1, {i: 1 for i in range(n + 1)})
	prim[0] = prim[1] = 0
	i = 2
	while i * i <= n:
		if prim[i]:
			for j in range(i * 2, n + 1, i):
				prim[j] = 0
		i += 1
	return list(filter(lambda x: prim[x], prim.keys()))
from sys import stdin
from collections import *
from bisect import *
(n, m) = arr_inp(1)
(mat, primes, ans, col) = ([arr_inp(1) for i in range(n)], count_prime(100003), float('inf'), defaultdict(int))
for i in range(n):
	r = 0
	for j in range(m):
		ix = bisect_right(primes, mat[i][j])
		if primes[ix - 1] == mat[i][j]:
			ix -= 1
		col[j] += primes[ix] - mat[i][j]
		r += primes[ix] - mat[i][j]
		if i == n - 1:
			ans = min(ans, col[j])
	ans = min(ans, r)
print(ans)


maxim = 100005
prime = [True] * maxim
prime[0] = False
prime[1] = False
for i in range(2, maxim):
	if prime[i]:
		for j in range(i + i, maxim, i):
			prime[j] = False
(n, m) = map(int, input().split())
rows = [0] * n
cols = [0] * m
for i in range(n):
	arr = list(map(int, input().split()))
	for j in range(m):
		x = arr[j]
		while not prime[x]:
			x += 1
		rows[i] += x - arr[j]
		cols[j] += x - arr[j]
print(min(min(rows), min(cols)))


num1 = 102001
num2 = 2
prime = [1] * num1
prime[1] = 0
prime[0] = 0
for i in range(num2, num1):
	j = i
	while j + i < num1:
		j += i
		prime[j] = 0
l = []
(n, m) = map(int, input().split())
for i in range(n):
	t = list(map(int, input().split()))
	l.append(t)
ans = 100000
for i in range(n):
	tot = 0
	for j in range(m):
		result = l[i][j]
		for k in range(result, num1):
			if prime[k] == 1:
				tot += k - result
				break
	ans = min(ans, tot)
for j in range(m):
	tot = 0
	for i in range(n):
		result = l[i][j]
		for k in range(result, num1):
			if prime[k] == 1:
				tot += k - result
				break
	ans = min(ans, tot)
print(ans)


maxn = 100100
ar = [1 for i in range(maxn)]
(ar[0], ar[1]) = (0, 0)
for i in range(2, maxn):
	if ar[i]:
		for j in range(i, (maxn - 1) // i + 1):
			ar[i * j] = 0
dst = maxn
d = [dst for i in range(maxn)]
for i in reversed(range(maxn)):
	if ar[i]:
		dst = 0
	d[i] = min(d[i], dst)
	dst += 1
(n, m) = map(int, input().split())
g = [[int(x) for x in input().split()] for _ in range(n)]
g = [[d[x] for x in y] for y in g]
tmpsharon = min([sum(x) for x in g] + [sum(x) for x in zip(*g)])
print(tmpsharon)


def is_prime(x, primes):
	for i in primes:
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True
(n, m) = [int(x) for x in input().split()]
a = []
primes = []
for i in range(2, 110000):
	if is_prime(i, primes):
		primes.append(i)
next = [0] * 110000
next[0] = 2
for x in primes:
	val = x
	while next[x] == 0:
		next[x] = val
		x -= 1
for i in range(n):
	a.append([int(x) for x in input().split()])
for i in range(n):
	for j in range(m):
		a[i][j] = next[a[i][j]] - a[i][j]
print(min(min((sum(x) for x in a)), min((sum(x) for x in zip(*a)))))


import math
import sys, string, bisect
input = sys.stdin.readline
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : list(map(int, input().split()))
I = lambda : int(input())

def find_ge(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a):
		return a[i]
	raise ValueError
MAX_SIZE = 1000005
isprime = [True] * MAX_SIZE
prime = []
SPF = [None] * MAX_SIZE

def manipulated_seive(N):
	isprime[0] = isprime[1] = False
	for i in range(2, N):
		if isprime[i] == True:
			prime.append(i)
			SPF[i] = i
		j = 0
		while j < len(prime) and i * prime[j] < N and (prime[j] <= SPF[i]):
			isprime[i * prime[j]] = False
			SPF[i * prime[j]] = prime[j]
			j += 1
manipulated_seive(MAX_SIZE)
(n, m) = M()
g = []
f = [0] * m
mi = MAX_SIZE
for i in range(n):
	l = L()
	for k in range(m):
		l[k] = find_ge(prime, l[k]) - l[k]
		f[k] += l[k]
	g.append(l)
	r = sum(l)
	if r < mi:
		mi = r
print(min(min(f), mi))


import sys
import string
import math
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
from fractions import Fraction

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def tmi(s):
	return tuple(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def js(lst):
	return ' '.join((str(d) for d in lst))

def jsns(lst):
	return ''.join((str(d) for d in lst))

def line():
	return sys.stdin.readline().strip()

def linesp():
	return line().split()

def iline():
	return int(line())

def mat(n):
	matr = []
	for _ in range(n):
		matr.append(linesp())
	return matr

def matns(n):
	mat = []
	for _ in range(n):
		mat.append([c for c in line()])
	return mat

def mati(n):
	mat = []
	for _ in range(n):
		mat.append(lmi(line()))
	return mat

def pmat(mat):
	for row in mat:
		print(js(row))

def prime(n):
	primes = [True for _ in range(n + 1)]
	primes[0] = False
	primes[1] = False
	for i in range(2, n + 1):
		if i * i > n:
			break
		if primes[i]:
			for j in range(i * i, n + 1, i):
				primes[j] = False
	p = []
	for (e, b) in enumerate(primes):
		if b:
			p.append(e)
	return p
primes = prime(10 ** 5 + 1000)

def dist(num):
	lo = 0
	hi = len(primes) - 1
	cost = 0
	while lo <= hi:
		if lo == hi:
			return primes[lo] - num
		elif lo == hi - 1:
			if primes[lo] >= num:
				return primes[lo] - num
			else:
				return primes[hi] - num
		mid = (lo + hi) // 2
		if primes[mid] >= num:
			hi = mid
		else:
			lo = mid

def costr(mat, row):
	cost = 0
	for j in range(len(mat[row])):
		cost += dist(mat[row][j])
	return cost

def costj(mat, col):
	cost = 0
	for i in range(len(mat)):
		cost += dist(mat[i][col])
	return cost

def main():
	(n, _) = mi(line())
	mat = mati(n)
	mm = float('inf')
	for i in range(len(mat)):
		mm = min(mm, costr(mat, i))
	for j in range(len(mat[0])):
		mm = min(mm, costj(mat, j))
	print(mm)
main()


primes = [True] * (2 * 10 ** 5 + 1)
for i in range(2, int((2 * 10 ** 5 + 1) ** 0.5 + 1)):
	if primes[i]:
		for j in range(2 * i, len(primes), i):
			primes[j] = False
primes = [i for i in range(2, len(primes)) if primes[i]]

def bin_search(n):
	l = 0
	r = len(primes)
	while l <= r:
		mid = (l + r) // 2
		if primes[mid] == n:
			return n
		elif primes[mid] < n:
			l = mid + 1
		else:
			r = mid - 1
	return primes[(l + r) // 2 + 1]
(n, m) = map(int, input().split())
arr = []
for i in range(n):
	arr.append(list(map(int, input().split())))
min_cost = float('inf')
for i in range(n):
	temp = 0
	for j in range(m):
		temp += abs(arr[i][j] - bin_search(arr[i][j]))
	min_cost = min(min_cost, temp)
for j in range(m):
	temp = 0
	for i in range(n):
		temp += abs(arr[i][j] - bin_search(arr[i][j]))
	min_cost = min(min_cost, temp)
print(min_cost)


def find_primes(prime_len):
	flag_list = [True] * prime_len
	flag_list[0] = flag_list[1] = False
	prime_list = []
	for i in range(2, int(prime_len ** 0.5)):
		if flag_list[i]:
			for n in range(i + i, len(flag_list), i):
				flag_list[n] = False
	for idx in range(len(flag_list)):
		if flag_list[idx]:
			prime_list.append(idx)
	return (prime_list, flag_list)

def next_val_binary_search(val, search_list, idx_low, idx_hi):
	idx_mid = int((idx_hi + idx_low) / 2)
	if idx_mid == idx_low:
		if val < search_list[0]:
			next_prime = search_list[0]
			return next_prime
		next_prime = search_list[idx_hi]
		return next_prime
	if val > search_list[idx_mid]:
		new_idx_low = idx_mid
		next_prime = next_val_binary_search(val, search_list, new_idx_low, idx_hi)
		return next_prime
	else:
		new_idx_hi = idx_mid
		next_prime = next_val_binary_search(val, search_list, idx_low, new_idx_hi)
		return next_prime
(prime_list, flag_list) = find_primes(10 ** 5 + 5)
max_dif = 0
dimentions = input()
dimentions = dimentions.split()
for i in range(len(dimentions)):
	dimentions[i] = int(dimentions[i])
input_matrix = []
for r in range(dimentions[0]):
	row = input()
	row = row.split()
	for n in range(len(row)):
		row[n] = int(row[n])
	input_matrix.append(row)
moves = 10 ** 5
for row in input_matrix:
	row_moves = 0
	for val in row:
		if not flag_list[val]:
			next_prime = next_val_binary_search(val, prime_list, 0, len(prime_list) - 1)
			dist_to_next_prime = next_prime - val
			row_moves += dist_to_next_prime
	moves = min(moves, row_moves)
for col in range(dimentions[1]):
	col_moves = 0
	for row in input_matrix:
		val = row[col]
		if not flag_list[val]:
			next_prime = next_val_binary_search(val, prime_list, 0, len(prime_list) - 1)
			dist_to_next_prime = next_prime - val
			col_moves += dist_to_next_prime
	moves = min(moves, col_moves)
print(moves)


def buil_prime_dict(n):
	lst = [0, 0] + [1] * n
	for i in range(2, n):
		if lst[i]:
			for j in range(i * i, n, i):
				lst[j] = 0
	for k in range(n, -1, -1):
		if lst[k]:
			ind = k
			lst[k] = 0
		else:
			lst[k] = ind - k
	return lst
prime_dict = buil_prime_dict(10 ** 5 + 100)
line1 = input()
n = int(line1.split(' ')[0])
m = int(line1.split(' ')[1])
matrix = []
max_num = 0
for j in range(n):
	line2 = input()
	d = [int(x) for x in line2.split(' ')]
	matrix.append(d)
matrix = [[prime_dict[y] for y in i] for i in matrix]
results = []
for x in matrix:
	results.append(sum(x))
for x in zip(*matrix):
	results.append(sum(x))
print(min(results))


import heapq
from bisect import bisect_left, bisect_right
from collections import Counter
from itertools import accumulate
import math
R = lambda : list(map(int, input().split()))

def is_prime(num):
	return not any([num % i == 0 for i in range(2, int(math.sqrt(num) + 1))])
(n, m) = R()
grid = [list(R()) for i in range(n)]
primes = [x for x in range(2, 10 ** 5 + 100) if is_prime(x)]
for i in range(n):
	for j in range(m):
		grid[i][j] = primes[bisect_left(primes, grid[i][j])] - grid[i][j]
min_row = min([sum(r) for r in grid])
min_col = min([sum(c) for c in zip(*grid)])
print(min(min_row, min_col))


import bisect

def seive():
	seive_arr = [True] * 1000100
	seive_arr[0] = False
	seive_arr[1] = False
	for i in range(2, 1000002):
		if seive_arr[i]:
			for j in range(i * i, 1000002, i):
				seive_arr[j] = False
	primes = []
	for i in range(1000002):
		if seive_arr[i]:
			primes.append(i)
	return primes
primes = seive()
(m, n) = map(int, input().split())
mat = []
for i in range(m):
	l = list(map(int, input().split()))
	mat.append(l)
mat2 = []
for i in range(m):
	temp = []
	for j in range(n):
		val = mat[i][j]
		closest = bisect.bisect_left(primes, val)
		ok = primes[closest] - val
		temp.append(ok)
	mat2.append(temp)
minVal = 100000000000
for i in mat2:
	minVal = min(minVal, sum(i))
for i in range(n):
	s = 0
	for j in range(m):
		s += mat2[j][i]
	minVal = min(minVal, s)
print(minVal)


from math import *
sz = 100010
ind = []
prime = []
for x in range(sz):
	ind.append(False)

def seive():
	for x in range(3, sz, 2):
		for y in range(x * x, sz, 2 * x):
			ind[y] = True
	prime.append(2)
	for x in range(3, sz, 2):
		if not ind[x]:
			prime.append(x)

def lb():
	k = 0
	for x in range(100001):
		if prime[k] < x:
			k += 1
		ind[x] = prime[k]
seive()
lb()
b = input()
b = b.split()
ans = []
for x in range(int(b[0])):
	c = input()
	c = c.split()
	for y in c:
		cnt = ind[int(y)] - int(y)
		ans.append(cnt)
l = 100000000000
i = 0
for x in range(int(b[0])):
	cnt = 0
	for y in range(int(b[1])):
		cnt += ans[i]
		i += 1
	l = min(l, cnt)
j = 0
for x in range(int(b[1])):
	cnt = 0
	i = j
	for y in range(int(b[0])):
		cnt += ans[i]
		i += int(b[1])
	l = min(l, cnt)
	j += 1
print(l)


import bisect

def sieve(n):
	p = 2
	prime = [True for i in range(n + 1)]
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	c = []
	for p in range(2, n):
		if prime[p]:
			c.append(p)
	return c

def transpose(a, n, m):
	c = []
	for i in range(max(n, m)):
		l = []
		for j in range(max(n, m)):
			try:
				l.append(a[j][i])
			except:
				pass
		c.append(l)
	c = c[:m]
	return c

def calcost(a, c):
	cost = 0
	for i in range(len(a)):
		p = bisect.bisect_left(c, a[i])
		cost += c[p] - a[i]
	return cost
c = sieve(1000001)
(n, m) = list(map(int, input().split()))
l = []
for i in range(n):
	a = list(map(int, input().split()))
	l.append(a)
cost = []
for i in range(len(l)):
	cost.append(calcost(l[i], c))
l = transpose(l, n, m)
for i in range(len(l)):
	cost.append(calcost(l[i], c))
print(min(cost))


import sys
import math as mt
import bisect as bi
import collections as cc
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
N = 10 ** 5 + 100
prime = []
pr = [0] * N
pr[0] = pr[1] = 1
for i in range(2, N):
	if not pr[i]:
		prime.append(i)
		for j in range(2 * i, N, i):
			pr[j] = 1
(n, m) = I()
ar = [I() for i in range(n)]
cst = [[0] * m for i in range(n)]
for i in range(n):
	for j in range(m):
		now = ar[i][j]
		x = bi.bisect_left(prime, now)
		cst[i][j] = abs(now - prime[x])
ans = float('inf')
for i in cst:
	ans = min(ans, sum(i))
for i in zip(*cst):
	ans = min(ans, sum(i))
print(ans)


import math
(n, m) = input().split(' ')
line = int(n)
column = int(m)
limit = 100025
primes_list = [True for i in range(limit + 1)]
next_prime_distance = [0 for i in range(200000)]

def sieve_primes():
	primes_list[0] = primes_list[1] = False
	for i in range(2, int(math.sqrt(limit))):
		if primes_list[i]:
			j = 2
			while i * j <= limit:
				primes_list[i * j] = False
				j += 1

def next_prime():
	for i in range(limit - 1, -1, -1):
		if primes_list[i]:
			next_prime_distance[i] = 0
		else:
			next_prime_distance[i] = 1 + next_prime_distance[i + 1]
sieve_primes()
next_prime()
matrix = []
for row in range(line):
	number = input().split(' ')
	matrix.append([int(char) for char in number])
r = [0] * line
c = [0] * column
for i in range(line):
	for j in range(column):
		value = int(matrix[i][j])
		distance = next_prime_distance[value]
		r[i] += distance
		c[j] += distance
less_row = min(r)
less_column = min(c)
print(min(less_row, less_column))


(n, m) = list(map(int, input().split()))
arr = [list(map(int, input().split())) for _ in range(n)]
N = int(100000.0 + 4)
is_prime = [0] * N
is_prime[0] = is_prime[1] = 1
for i in range(2, N):
	if is_prime[i] == 1:
		continue
	for j in range(i * 2, N, i):
		is_prime[j] = 1
is_prime[-1] = N - 1
for i in range(N - 2, 0, -1):
	if is_prime[i] == 1:
		is_prime[i] = is_prime[i + 1]
	else:
		is_prime[i] = i
(r, c) = ([0] * n, [0] * m)
for i in range(n):
	for j in range(m):
		r[i] += is_prime[arr[i][j]] - arr[i][j]
		c[j] += is_prime[arr[i][j]] - arr[i][j]
print(min(r + c))


from bisect import bisect_left

def sieve(r):
	D = dict()
	yield 2
	for q in range(3, r, 2):
		p = D.pop(q, None)
		if not p:
			D[q * q] = q
			yield q
		else:
			x = p + q
			while x in D or not x & 1:
				x += p
			D[x] = p
primes = list(sieve(1000003))
II = lambda : list(map(int, input().split()))
(n, m) = II()
grid = [[primes[bisect_left(primes, x)] - x for x in II()] for _ in range(n)]
print(min(min((sum(row) for row in grid)), min((sum(col) for col in zip(*grid)))))


p = 10 ** 5 + 10

def sieve():
	l = [True] * p
	i = 2
	while i * i <= p:
		if l[i]:
			for j in range(i * i, p, i):
				l[j] = False
		i += 1
	primes = []
	for i in range(2, p):
		if l[i]:
			primes.append(i)
	return primes
primes = sieve()
from bisect import bisect_left as bl
(n, m) = map(int, input().split())
req = [[0 for i in range(m)] for j in range(n)]
mat = []
for i in range(n):
	mat.append([int(i) for i in input().split()])
for i in range(n):
	for j in range(m):
		curr = mat[i][j]
		ind = bl(primes, curr)
		g = primes[ind]
		req[i][j] = g - curr
mini = 1000000000
for i in range(n):
	curr = sum(req[i])
	if curr < mini:
		mini = curr
for j in range(m):
	curr = 0
	for i in range(n):
		curr += req[i][j]
	if curr < mini:
		mini = curr
print(mini)


def buil_prime_dict(n):
	a = [x for x in range(n + 1)]
	a[1] = 0
	lst = []
	i = 2
	while i <= n:
		if a[i] != 0:
			lst.append(a[i])
			for j in range(i, n + 1, i):
				a[j] = 0
		i += 1
	return lst
prime_dict = buil_prime_dict(10 ** 5 + 100)

def diff_search_number_prime(a, dictionary):
	start_ind = 0
	stop_ind = len(dictionary) - 1
	if a == 1:
		return 1
	while stop_ind - start_ind != 1:
		middle_ind = (stop_ind - start_ind) // 2 + start_ind
		if a == dictionary[middle_ind] or a == dictionary[start_ind] or a == dictionary[stop_ind]:
			return 0
		elif a > dictionary[middle_ind]:
			start_ind = middle_ind
		else:
			stop_ind = middle_ind
	return abs(a - dictionary[stop_ind])
line1 = input()
n = int(line1.split(' ')[0])
m = int(line1.split(' ')[1])
matrix = []
max_num = 0
for j in range(n):
	line2 = input()
	d = [int(x) for x in line2.split(' ')]
	matrix.append(d)
	if max_num < max(d):
		max_num = max(d)
dict_dist = [0, 1]
for i in range(2, max_num + 1):
	dict_dist.append(diff_search_number_prime(i, prime_dict))
matrix = [[dict_dist[y] for y in i] for i in matrix]
results = []
for x in matrix:
	results.append(sum(x))
for x in zip(*matrix):
	results.append(sum(x))
print(min(results))


import sys, math, bisect
inf = float('inf')
mod = inf + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def freq(a, x):
	z = upperBound(a, x) - lowerBound(a, x)
	if z <= 0:
		return 0
	return z

def bs(arr, x):
	l = 0
	r = len(arr) - 1
	ans = 10 ** 9
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] >= x:
			ans = min(ans, arr[mid])
			r = mid - 1
		else:
			l = mid + 1
	return ans

def SieveOfEratosthenes(n):
	ans = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans
arr = SieveOfEratosthenes(10 ** 5 + 100)
for _ in range(1):
	(n, m) = map(int, input().split())
	matt = []
	for i in range(n):
		matt.append(list(map(int, input().split())))
	ans = [[-1 for i in range(m)] for j in range(n)]
	for i in range(n):
		for j in range(m):
			ans[i][j] = bs(arr, matt[i][j]) - matt[i][j]
	res = 10 ** 9
	for i in range(n):
		res = min(sum(ans[i]), res)
	for i in range(m):
		curr = 0
		for j in range(n):
			curr += ans[j][i]
		res = min(curr, res)
	print(res)


import sys
import math
limit = 100025
list_primes = [True for i in range(limit + 1)]
next_primes = [0 for i in range(200000)]

def SieveOfEratosthenes():
	list_primes[0] = list_primes[1] = False
	for i in range(2, int(math.sqrt(limit))):
		if list_primes[i]:
			j = 2
			while i * j <= limit:
				list_primes[i * j] = False
				j += 1

def get_next_primes():
	for i in range(limit - 1, -1, -1):
		if list_primes[i]:
			next_primes[i] = 0
		else:
			next_primes[i] = 1 + next_primes[i + 1]
SieveOfEratosthenes()
get_next_primes()
sizes = input().split(' ')
(n, m) = (int(sizes[0]), int(sizes[1]))
matrix = []
for i in range(0, n):
	matrix.append(input().split(' '))
moves = 100000
for index_row in range(n):
	best_row = 0
	for index_column in range(m):
		num = int(matrix[index_row][index_column])
		best_row += next_primes[num]
	if best_row < moves:
		moves = best_row
for index_column in range(m):
	best_column = 0
	for index_row in range(n):
		num = int(matrix[index_row][index_column])
		best_column += next_primes[num]
	if best_column < moves:
		moves = best_column
print(moves)


(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
isPrime = [False, False] + [True] * 101000
for i in range(2, len(isPrime)):
	if isPrime[i]:
		for j in range(i * i, len(isPrime), i):
			isPrime[j] = False
nextPrime = [0] * len(isPrime)
for i in range(len(isPrime) - 2, 0, -1):
	if isPrime[i]:
		nextPrime[i] = i
	else:
		nextPrime[i] = nextPrime[i + 1]
row_scores = [0] * n
col_scores = [0] * m
for i in range(n):
	for j in range(m):
		row_scores[i] += nextPrime[a[i][j]] - a[i][j]
		col_scores[j] += nextPrime[a[i][j]] - a[i][j]
print(min(row_scores + col_scores))


import os
import sys
import math
import heapq
from decimal import *
from io import BytesIO, IOBase
from collections import defaultdict, deque

def r():
	return int(input())

def rm():
	return map(int, input().split())

def rl():
	return list(map(int, input().split()))

def prime(p):
	if p == 1:
		return 0
	if p == 2 or p == 3:
		return 1
	if p % 2 == 0 or p % 3 == 0:
		return 0
	for i in range(5, int(math.sqrt(p)) + 1, 6):
		if p % i == 0 or p % (i + 2) == 0:
			return 0
	return 1

def SieveOfEratosthenes(n):
	prime = [1 for i in range(n + 1)]
	prime[0] = prime[1] = 0
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = 0
		p += 1
	primes = []
	for (i, j) in enumerate(prime):
		if j:
			primes.append(i)
	return primes
(n, m) = rm()
a = []
for i in range(n):
	a.append(rl())
primes = SieveOfEratosthenes(2 * 10 ** 5)
p = []
nn = len(primes)
for i in a:
	p.append([])
	for j in i:
		if prime(j):
			p[-1].append(0)
		else:
			lo = 0
			hi = nn - 1
			while lo < hi:
				mid = (lo + hi) // 2
				if primes[mid] < j:
					lo = mid + 1
				else:
					hi = mid
			p[-1].append(primes[hi] - j)
rowSum = [0] * n
colSum = [0] * m
for i in range(n):
	for j in range(m):
		rowSum[i] += p[i][j]
		colSum[j] += p[i][j]
print(min(min(rowSum), min(colSum)))


from sys import stdin

def f(i, s):
	if s[i] == 0:
		return 0
	k = 0
	while s[i] != 0:
		if i == 111111:
			return k
		i += 1
		k += 1
	return k

def r(A, s, mi):
	for _ in range(n):
		k = [f(int(i), s) for i in stdin.readline().split()]
		sk = sum(k)
		mi = min(mi, sk)
		if sk == 0:
			return 0
		A.append(k)
	for i in range(len(A[0])):
		col = 0
		for j in range(len(A)):
			col += A[j][i]
		mi = min(mi, col)
	return mi
(n, m) = [int(i) for i in stdin.readline().split()]
s = [0] * 111111
s[1] = 1
for i in range(2, len(s)):
	if s[i]:
		continue
	for j in range(i * i, len(s), i):
		s[j] = 1
mi = float('inf')
print(r([], s, mi))


import math
(n, m) = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

def seive():
	s = 10 ** 5 + 10
	primes = [True] * s
	primes[0] = False
	primes[1] = False
	for i in range(2, int(math.sqrt(s)) + 1):
		j = 2
		while j * i < s:
			primes[i * j] = False
			j += 1
	return primes
primes = seive()
near = list(range(0, 10 ** 5 + 10))
for i in range(10 ** 5 + 9, 0, -1):
	if primes[i]:
		cur = i
		near[i] = 0
		j = i
		break
for i in range(j - 1, -1, -1):
	if primes[i]:
		cur = i
		near[i] = 0
	else:
		near[i] = abs(cur - near[i])
cols = [0] * m
rows = [0] * n
k = float('INF')
for i in range(n):
	temp = 0
	for j in range(m):
		temp += near[grid[i][j]]
	k = min(k, temp)
for i in range(m):
	temp = 0
	for j in range(n):
		temp += near[grid[j][i]]
	k = min(k, temp)
print(k)


def main():
	entrada = input().split(' ')
	valor1 = int(entrada[0])
	valor2 = int(entrada[1])
	num1 = 100025
	num2 = 2
	matriz = []
	primos = [True] * num1
	primos = set_numeros_nao_primos(num1, num2, primos)
	for i in range(valor1):
		linha = list(map(int, input().split()))
		matriz.append(linha)
	resposta = 100000
	resposta = min(resposta, calcula_linha(resposta, valor1, valor2, matriz, num1, primos))
	resposta = min(resposta, calcula_coluna(resposta, valor1, valor2, matriz, num1, primos))
	print(resposta)

def calcula_linha(res, n, m, matriz, num1, primos):
	for i in range(n):
		movimentos = 0
		for j in range(m):
			result = matriz[i][j]
			for k in range(result, num1):
				if primos[k] == True:
					movimentos += k - result
					break
		res = min(res, movimentos)
	return res

def calcula_coluna(res, n, m, matriz, num1, primos):
	for i in range(m):
		movimentos = 0
		for j in range(n):
			result = matriz[j][i]
			for k in range(result, num1):
				if primos[k] == True:
					movimentos += k - result
					break
		res = min(res, movimentos)
	return res

def set_numeros_nao_primos(num1, num2, numerosPrimos):
	for i in range(num2, num1):
		j = i
		while j + i < num1:
			j += i
			numerosPrimos[j] = False
	numerosPrimos[1] = False
	numerosPrimos[0] = False
	return numerosPrimos
main()


def sieve(n):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
(a, m) = map(int, input().split())
no = 100100
prime = [True for i in range(no + 1)]
sieve(no)
prime[0] = False
prime[1] = False
req = [0] * no
for i in range(no - 2, -1, -1):
	if prime[i]:
		req[i] = 0
	else:
		req[i] = req[i + 1] + 1
mat = []
for i in range(a):
	b = list(map(int, input().split()))
	mat.append(b)
ans = 10000000000
for i in range(a):
	temp = 0
	for j in range(m):
		temp += req[mat[i][j]]
	ans = min(ans, temp)
for i in range(m):
	temp = 0
	for j in range(a):
		temp += req[mat[j][i]]
	ans = min(ans, temp)
print(ans)


def rotated(array_2d):
	list_of_tuples = zip(*array_2d[::-1])
	return list([list(elem) for elem in list_of_tuples])
n = 100100
p = [0, 0] + [1] * n
(p[0], p[1]) = (0, 0)
n1 = int(n ** 0.5)
for i in range(2, n1):
	if p[i] == 1:
		for j in range(i * i, n, i):
			p[j] = 0
for k in range(n, -1, -1):
	if p[k]:
		ind = k
		p[k] = 0
	else:
		p[k] = ind - k
lst = []
(x, y) = map(int, input().split())
for j in range(x):
	l = []
	for i in map(int, input().split()):
		l.append(p[i])
	lst.append(l)
st = []
for x in lst:
	st.append(sum(x))
for x in rotated(lst):
	st.append(sum(x))
print(min(st))


from sys import stdin
max_val = int(10000000000000.0)
min_val = int(-10000000000000.0)

def read_int():
	return int(stdin.readline())

def read_ints():
	return [int(x) for x in stdin.readline().split()]

def read_str():
	return input()

def read_strs():
	return [x for x in stdin.readline().split()]
limit = 110000
primes = [0, 0] + [1] * limit
for i in range(2, limit):
	if primes[i]:
		for j in range(i * i, limit, i):
			primes[j] = 0
u = limit
for i in reversed(range(limit)):
	if primes[i]:
		u = i
	primes[i] = u - i
(n, m) = [int(x) for x in input().split()]
matrix = [[int(x) for x in input().split()] for _ in range(n)]
maxs = 10 ** 10
for v in matrix:
	maxs = min(maxs, sum([primes[x] for x in v]))
for v in zip(*matrix):
	maxs = min(maxs, sum([primes[x] for x in v]))
print(maxs)


isPrime = [1] * 100010

def Prime():
	global isPrime
	isPrime[0] = isPrime[1] = 0
	for i in range(100010):
		if isPrime[i]:
			for j in range(2 * i, 100010, i):
				isPrime[j] = 0
Prime()
(n, m) = map(int, input().split())
l = []
for i in range(n):
	l.append([int(x) for x in input().split()])
	for j in range(m):
		temp = l[-1][j]
		while True:
			if isPrime[temp]:
				l[-1][j] = temp - l[-1][j]
				break
			temp += 1
s = 1000000000
for i in range(n):
	if s > sum(l[i]):
		s = sum(l[i])
for j in range(m):
	temp = 0
	for i in range(n):
		temp += l[i][j]
	if s > temp:
		s = temp
print(s)


def find_primes(prime_len):
	flag_list = [True] * prime_len
	flag_list[0] = flag_list[1] = False
	prime_list = []
	for i in range(2, int(prime_len ** 0.5)):
		if flag_list[i]:
			for n in range(i + i, len(flag_list), i):
				flag_list[n] = False
	for idx in range(len(flag_list)):
		if flag_list[idx]:
			prime_list.append(idx)
	return prime_list

def find_next_prime(prime_list, n):
	sol = [0] * (n + 1)
	curr_prime_idx = 0
	for i in range(n + 1):
		if i > prime_list[curr_prime_idx]:
			curr_prime_idx += 1
		sol[i] = prime_list[curr_prime_idx]
	return sol
prime_list = find_primes(10 ** 5 + 5)
next_prime = find_next_prime(prime_list, 10 ** 5)
max_dif = 0
dimentions = input()
dimentions = dimentions.split()
for i in range(len(dimentions)):
	dimentions[i] = int(dimentions[i])
input_matrix = []
for r in range(dimentions[0]):
	row = input()
	row = row.split()
	for n in range(len(row)):
		row[n] = int(row[n])
	input_matrix.append(row)
moves = 10 ** 5
for row in input_matrix:
	row_moves = 0
	for val in row:
		dist_to_next_prime = next_prime[val] - val
		row_moves += dist_to_next_prime
	moves = min(moves, row_moves)
for col in range(dimentions[1]):
	col_moves = 0
	for row in input_matrix:
		val = row[col]
		dist_to_next_prime = next_prime[val] - val
		col_moves += dist_to_next_prime
	moves = min(moves, col_moves)
print(moves)


import math
(n, m) = map(int, input().rstrip().split())
row = [0] * n
col = [0] * m

def isPrime(x):
	if x in [2, 3, 5, 7, 11, 13, 17, 19]:
		return True
	if x == 1:
		return False
	for i in range(2, int(math.sqrt(x)) + 2):
		if x % i == 0:
			return False
	return True
primes = [0] * 100011
for i in range(1, 100011):
	if isPrime(i):
		primes[i] = 1
for i in range(n):
	li = list(map(int, input().rstrip().split()))
	for j in range(m):
		x = li[j]
		while primes[x] != 1:
			x += 1
		row[i] += x - li[j]
		col[j] += x - li[j]
minm = min(row + col)
print(minm)


N_MAX = 10 ** 5 + 7
(N, M) = (0, 0)
matrix = [[]]
closest_prime = [[]]
prime = [True] * N_MAX

def sieve():
	global prime
	global closest_prime
	prime[0] = False
	prime[1] = False
	closest_prime = [0] * N_MAX

	def backtrack(value):
		closest_prime[value] = value
		for i in range(value - 1, -1, -1):
			if prime[i]:
				return
			closest_prime[i] = value
	for i in range(2, 10 ** 5 + 7):
		if prime[i] == True:
			backtrack(i)
			for j in range(i * i, 10 ** 5 + 7, i):
				prime[j] = False

def entrypoint():
	global N, M, matrix
	(N, M) = list(map(int, input().split()))
	read_row = lambda : list(map(int, input().split()))
	matrix = [read_row() for i in range(N)]

def compute_cost(index, type='ROW'):
	values = []
	if type == 'ROW':
		values = matrix[index]
	elif type == 'COL':
		values = [matrix[j][index] for j in range(N)]
	value_cost = lambda x: closest_prime[x] - x
	cost = sum([value_cost(value) for value in values])
	return cost

def compute_min_moves():
	costs = []
	costs += [compute_cost(i, type='ROW') for i in range(N)]
	costs += [compute_cost(i, type='COL') for i in range(M)]
	print(min(costs))

def main():
	sieve()
	entrypoint()
	compute_min_moves()
main()


nearest_prime = [0] * 100004

def sieve(n):
	primes = [True] * (n + 1)
	primes[0] = False
	primes[1] = False
	for (index, i) in enumerate(primes):
		if i == True:
			for j in range(index * index, n + 1, index):
				primes[j] = False
	return primes

def sub_from_nearest(a):
	return nearest_prime[a] - a

def main():
	(m, n) = [int(x) for x in input().split()]
	prime_bool = sieve(100003)
	nearest = -1
	for (i, bool) in list(enumerate(prime_bool))[::-1]:
		if bool:
			nearest = i
			nearest_prime[i] = i
		else:
			nearest_prime[i] = nearest
	matrix = []
	for i in range(0, m):
		lis = [sub_from_nearest(int(x)) for x in input().split()]
		matrix.append(lis)
	min = 10000000
	for i in matrix:
		su = sum(i)
		if su < min:
			min = su
	for i in range(0, n):
		su = sum([row[i] for row in matrix])
		if su < min:
			min = su
	print(min)

def __starting_point():
	main()
__starting_point()


import copy
from bisect import bisect_left
primes = []

def sieve():
	M = int(1000000.0)
	prime = [True for i in range(M + 1)]
	p = 2
	while p * p <= M:
		if prime[p]:
			for i in range(p * 2, M + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(M + 1):
		if prime[p]:
			primes.append(p)
sieve()
(n, m) = map(int, input().split())
o = [list(map(int, input().split())) for _ in range(n)]
v = copy.deepcopy(o)
for (j, x) in enumerate(v):
	for (i, y) in enumerate(x):
		v[j][i] = primes[bisect_left(primes, y)]
sol = 10000000000.0
for (a, b) in zip(o, v):
	ctn = 0
	for (x, y) in zip(a, b):
		ctn += abs(x - y)
	if ctn < sol:
		sol = ctn
for (a, b) in zip(zip(*o), zip(*v)):
	ctn = 0
	for (x, y) in zip(a, b):
		ctn += abs(x - y)
	if ctn < sol:
		sol = ctn
print(sol)


import itertools as it
simple_nums = []

def sieve():
	yield 2
	D = {}
	for q in it.count(3, 2):
		p = D.pop(q, 0)
		if p:
			x = q + p
			while x in D:
				x += p
			D[x] = p
		else:
			yield q
			D[q * q] = 2 * q
simple_nums = list(it.islice(sieve(), 0, 10000))

def resize_simple():
	a = it.islice(sieve(), len(simple_nums), len(simple_nums) + 1)
	a = list(a)
	a = int(*a)
	simple_nums.append(a)

def get_nearest_to(num):
	if num <= simple_nums[0]:
		return simple_nums[0]
	while num > simple_nums[len(simple_nums) - 1]:
		resize_simple()
	high = len(simple_nums) - 1
	mid = high // 2
	low = 0
	while high - low > 1:
		mid = (low + high) // 2
		if simple_nums[mid] == num:
			return simple_nums[mid]
		if num > simple_nums[mid]:
			low = mid
		else:
			high = mid
	return simple_nums[high]

def get_steps(num):
	near = get_nearest_to(num)
	return near - num
(m, n) = map(int, input().split())
matrix = [[0 for i in range(n)] for j in range(m)]
simple_steps = [[0 for i in range(n)], [0 for i in range(m)]]
for i in range(m):
	buf = list(map(int, input().split()))
	for j in range(n):
		matrix[i][j] = buf[j]
		t = buf[j]
		a = get_steps(buf[j])
		simple_steps[0][j] += a
		simple_steps[1][i] += a
print(min(min(simple_steps[0]), min(simple_steps[1])))


limite = int(1000000.0)
primos = [True for i in range(limite)]
primos[0] = False
primos[1] = False
for i in range(2, limite):
	if primos[i]:
		for j in range(i ** 2, limite, i):
			primos[j] = False
distancias = [0 for i in range(200000)]
distancias[100000] = 3
for i in range(99999, -1, -1):
	if not primos[i]:
		distancias[i] = distancias[i + 1] + 1
entrada = input().split()
n = int(entrada[0])
m = int(entrada[1])
matriz = []
for i in range(n):
	entrada = input().split()
	matriz.append(list(map(int, entrada)))
menor_passo = limite
for i in range(n):
	passos = 0
	for j in range(m):
		passos += distancias[matriz[i][j]]
	if passos < menor_passo:
		menor_passo = passos
for j in range(m):
	passos = 0
	for i in range(n):
		passos += distancias[matriz[i][j]]
	if passos < menor_passo:
		menor_passo = passos
print(menor_passo)


from sys import stdin, gettrace
import bisect, sys
if not gettrace():

	def input():
		return next(stdin)[:-1]

def IP():
	return map(int, stdin.readline().split())

def L():
	return list(map(int, stdin.readline().split()))

def sieve():
	li = [True] * 1000001
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(1000001):
		if li[i] == True:
			prime.append(i)
	return prime

def main():

	def solve():
		(n, m) = map(int, stdin.readline().split())
		l = []
		for i in range(n):
			temp = list(map(int, stdin.readline().split()))
			l.append(temp)
		prime = sieve()
		changes = sys.maxsize
		for i in range(n):
			c = 0
			for j in range(m):
				ind = bisect.bisect_left(prime, l[i][j])
				c += prime[ind] - l[i][j]
			changes = min(changes, c)
		for j in range(m):
			c = 0
			for i in range(n):
				ind = bisect.bisect_left(prime, l[i][j])
				c += prime[ind] - l[i][j]
			changes = min(changes, c)
		print(changes)
		return
	solve()
main()


import bisect
top = 10 ** 5 + 10
pos = [True] * top
for i in range(2, top):
	if pos[i]:
		for j in range(2 * i, top, i):
			pos[j] = False
primes = [i for i in range(2, top) if pos[i]]
(n, m) = map(int, input().split())
rows = [0] * n
cols = [0] * m
for i in range(n):
	row = list(map(int, input().split()))
	for j in range(m):
		nearest = bisect.bisect_left(primes, row[j])
		rows[i] += primes[nearest] - row[j]
		cols[j] += primes[nearest] - row[j]
	if rows[i] == 0:
		exit(print(0))
print(min(min(rows), min(cols)))


def generate_primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	primes = []
	for p in range(n + 1):
		if prime[p]:
			primes.append(p)
	return primes

def calculate_distances(primes):
	pidx = 0
	distances = []
	for i in range(100001):
		if i > primes[pidx]:
			pidx += 1
		distances.append(primes[pidx] - i)
	return distances
primes = generate_primes(100003)
distances = calculate_distances(primes)
matrix = []
(n, _) = map(int, input().split())
for _ in range(n):
	matrix.append(list(map(int, input().split())))
dmx = list(map(lambda r: list(map(lambda x: distances[x], r)), matrix))
t_dmx = [[dmx[j][i] for j in range(len(dmx))] for i in range(len(dmx[0]))]
mdr = min(map(sum, dmx))
mdc = min(map(sum, t_dmx))
print(min(mdr, mdc))


import math

def findPrime(arr):
	largest = 100003
	for index in range(100000, 1, -1):
		isPrime = True
		root = math.floor(math.sqrt(index))
		for div in range(2, root + 1):
			if index % div == 0:
				isPrime = False
				arr[index] = largest
				break
		if isPrime:
			arr[index] = index
			largest = index

def solve(row, col, matrix):
	sieve = [0] * 100001
	findPrime(sieve)
	sieve[0] = 2
	sieve[1] = 2
	storeCol = [0] * col
	smallestRow = None
	for outerIndex in range(row):
		tempRow = 0
		for innerIndex in range(col):
			diff = sieve[matrix[outerIndex][innerIndex]] - matrix[outerIndex][innerIndex]
			tempRow += diff
			storeCol[innerIndex] += diff
		if smallestRow == None or tempRow < smallestRow:
			smallestRow = tempRow
	return min(min(storeCol), smallestRow)
(r, c) = list(map(int, input().split()))
matrix = []
for _ in range(r):
	matrix.append(list(map(int, input().split())))
print(solve(r, c, matrix))


from sys import stdin, stdout, setrecursionlimit
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm, accumulate
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
setrecursionlimit(10 ** 9)
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return input()

def num():
	return int(input())

def L():
	return list(sp())

def LF():
	return list(spf())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def spf():
	return map(int, input.readline().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def pmat2(A):
	for ele in A:
		for j in ele:
			print(j, end='')
		print()

def iseven(n):
	return n % 2 == 0

def seive(r):
	prime = [1 for i in range(r + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(r + 1):
		if prime[i]:
			for j in range(2 * i, r + 1, i):
				prime[j] = 0
	return prime
(n, m) = sp()
prime = seive(10 ** 5 + 100)
next_prime = [0] * 110000
primes = []
arr = []
next_prime[0] = 2
for i in range(2, len(prime)):
	if prime[i]:
		primes.append(i)
for i in primes:
	x = i
	while next_prime[i] == 0:
		next_prime[i] = x
		i -= 1
for _ in range(n):
	arr.append(L())
for i in range(n):
	for j in range(m):
		arr[i][j] = next_prime[arr[i][j]] - arr[i][j]
ans = []
a = []
for i in range(m):
	for j in range(n):
		a.append(arr[j][i])
	ans.append(a)
	a = []
print(min(min((sum(x) for x in arr)), min((sum(x) for x in ans))))
endtime = time.time()


import copy, bisect
from math import sqrt
primes = []
top = 10 ** 5 + 10
pos = [True] * top
for i in range(2, top):
	if pos[i]:
		for j in range(2 * i, top, i):
			pos[j] = False
primes = [i for i in range(2, top) if pos[i]]
arr = []
arr2 = []
k = 0
lst = []
(n, m) = map(int, input().split())
ans = 100000000
for i in range(n):
	arr.append(list(map(int, input().split())))
for i in arr:
	temp = 0
	for j in i:
		temp += primes[bisect.bisect_left(primes, j)] - j
	ans = min(ans, temp)
for _ in range(m):
	for i in range(len(arr)):
		lst.append(arr[i][k])
	k += 1
	arr2.append(copy.copy(lst))
	lst.clear()
for i in arr2:
	temp = 0
	for j in i:
		temp += primes[bisect.bisect_left(primes, j)] - j
	ans = min(ans, temp)
print(ans)


import math
from bisect import bisect_left
maxi = 100010
(n, m) = [int(x) for x in input().split()]
tag = [0] * maxi
lines = [0] * n
cols = [0] * m
prime = [0] * maxi
tag[0] = tag[1] = 1
count = 0
for i in range(2, maxi):
	if not tag[i]:
		prime[count] = i
		count += 1
	j = 0
	while j < count and prime[j] * i < maxi:
		tag[i * prime[j]] = 1
		if i % prime[j] == 0:
			break
		j += 1
matrix = []
prime = prime[0:count]
for i in range(n):
	col = [int(x) for x in input().split()]
	matrix.append(col)
for l in range(n):
	for c in range(m):
		x = matrix[l][c]
		if tag[x]:
			t = bisect_left(prime, x)
			lines[l] += prime[t] - x
			cols[c] += prime[t] - x
min_col = min(cols)
min_line = min(lines)
print(min(min_col, min_line))


from sys import stdin
input = stdin.readline

def get_primes(n):
	primes = []
	numbers = [x for x in range(1, n + 1)]
	checked = [False] * n
	for i in range(1, n):
		if checked[i]:
			continue
		divisor = numbers[i]
		primes.append(divisor)
		for j in range(i + divisor, n, divisor):
			checked[j] = True
	return primes
primes = get_primes(100005)
costs = [0]
i = 0
j = 0
for i in range(1, 100001):
	while primes[j] < i:
		j += 1
	costs.append(primes[j] - i)
(n, m) = [int(x) for x in input().split()]
a = [[int(x) for x in input().split()] for _ in range(n)]
ans = float('inf')
for r in range(n):
	current = 0
	for c in range(m):
		current += costs[a[r][c]]
	ans = min(ans, current)
for c in range(m):
	current = 0
	for r in range(n):
		current += costs[a[r][c]]
	ans = min(ans, current)
print(ans)


import math
prime = [2, 3, 5, 7, 11]
d = {}

def GeneratePrimes():
	for i in range(12, 100100):
		for j in prime:
			if i % j == 0:
				break
			if j * j > i:
				prime.append(i)
				break
		else:
			prime.append(i)
	for i in range(1, len(prime) + 1):
		d[prime[i - 1]] = i

def UpperBound(x):
	l = 0
	h = len(prime)
	while l <= h:
		m = (l + h) // 2
		if x > prime[m]:
			l = m + 1
		elif x < prime[m]:
			h = m - 1
		else:
			return m
	return l
GeneratePrimes()
(n, m) = map(int, input().split())
f = []
for i in range(n):
	ii = list(map(int, input().split()))
	f.append(ii)
mn = 10 ** 9
for i in range(n):
	now = 0
	for j in range(m):
		now += prime[UpperBound(f[i][j])] - f[i][j]
	mn = min(mn, now)
for i in range(m):
	now = 0
	for j in range(n):
		now += prime[UpperBound(f[j][i])] - f[j][i]
	mn = min(mn, now)
print(mn)


max = 150035
primes = [0 for x in range(max)]

def sieveOfEratosthenes():
	primes[1] = primes[0] = 1
	for i in range(2, max):
		if primes[i] == 0:
			for j in range(i + i, max, i):
				primes[j] = 1
	for i in range(max - 2, -1, -1):
		if primes[i] != 0:
			primes[i] += primes[i + 1]
sieveOfEratosthenes()
columns = [0 for x in range(max)]
(n, m) = map(int, input().split())
res = 1000000000.0
for i in range(0, n):
	aux = 0
	query = list(map(int, input().split()))
	for j in range(m):
		aux += primes[query[j]]
		columns[j] += primes[query[j]]
	if i == n - 1:
		for j in range(m):
			res = min(columns[j], res)
	res = min(aux, res)
print(res)


import os
import sys
from io import BytesIO, IOBase
from bisect import bisect_left

def sieve(n):
	dp = [1] * (n + 1)
	i = 2
	while i * i <= n:
		if dp[i]:
			for j in range(i * i, n + 1, i):
				dp[j] = 0
		i += 1
	primes = [2]
	for i in range(3, n + 1, 2):
		if dp[i]:
			primes.append(i)
	return primes

def main():
	primes = sieve(100000 + 100)
	(n, m) = map(int, input().split())
	arr = []
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	for r in range(n):
		for c in range(m):
			arr[r][c] = primes[bisect_left(primes, arr[r][c])] - arr[r][c]
	ans = 9999999999
	for i in range(n):
		ans = min(ans, sum(arr[i]))
	for i in range(m):
		temp = 0
		for j in range(n):
			temp += arr[j][i]
		ans = min(ans, temp)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
prm = [1 for i in range(101001)]
prm[0] = 0
prm[1] = 0
for i in range(2, int(math.sqrt(101001)) + 1):
	if prm[i] == 1:
		for j in range(i * i, 101001, i):
			prm[j] = 0
(n, m) = map(int, input().split())
arr = []
row = [0] * n
col = [0] * m
for i in range(n):
	l = list(map(int, input().split()))
	for k in range(m):
		x = l[k]
		while prm[l[k]] != 1:
			l[k] += 1
		row[i] += l[k] - x
		col[k] += l[k] - x
r = min(row)
c = min(col)
print(min(r, c))


import sys

def prime(n):
	v = int(n ** 0.5) + 1
	l = [True for i in range(n + 1)]
	l[0] = False
	l[1] = False
	for i in range(2, v):
		if l[i]:
			for j in range(i, n + 1, i):
				if j % i == 0 and j != i and l[j]:
					l[j] = False
	return l

def c_prime(n):
	if d.get(n, False):
		return d[n]
	elif table[n]:
		d[n] = n
		return d[n]
	elif n == 0 or n == 1:
		d[n] = 2
		return d[n]
	else:
		c = 1
		while True:
			if table[n + c]:
				d[n] = n + c
				return d[n]
			c += 1
table = prime(110000)
d = {}
(n, m) = [int(i) for i in input().split()]
s = sys.maxsize
matrix = []
for i in range(n):
	temp = [int(j) for j in input().split()]
	matrix.append(temp)
	s = min(s, sum([abs(j - c_prime(j)) for j in temp]))
for i in range(m):
	temp = [j[i] for j in matrix]
	s = min(s, sum([abs(j - c_prime(j)) for j in temp]))
print(s)


def I():
	return list(map(int, input().split()))

def sieve(n):
	p = 2
	primes = [True] * (n + 1)
	primes[1] = False
	primes[0] = False
	while p * p <= n:
		if primes[p]:
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return primes
(n, m) = I()
x = []
primes = sieve(100000)
diffToNextPrime = [0] * 100001
p = 100003
for i in range(100000, -1, -1):
	if primes[i]:
		p = i
	diffToNextPrime[i] = p - i
for i in range(n):
	x.append(I())
m = len(x[0])
ma = 99999999
for i in range(n):
	s = 0
	for j in range(m):
		x[i][j] = diffToNextPrime[x[i][j]]
		s += x[i][j]
	ma = min(s, ma)
for i in range(m):
	s = 0
	for j in range(n):
		s += x[j][i]
	ma = min(s, ma)
print(ma)


import bisect

def b_s(dp, ele):
	l = 0
	r = len(dp) - 1
	ans = 0
	while l <= r:
		mid = (l + r) // 2
		if dp[mid] == ele:
			return mid
		elif dp[mid] > ele:
			ans = mid
			r = mid - 1
		else:
			l = mid + 1
	return ans

def sieve(n):
	dp = [True] * (n + 1)
	i = 2
	dp[0] = False
	dp[1] = False
	dp[2] = True
	while i * i <= n:
		j = i
		for ii in range(j * j, n + 1, j):
			dp[ii] = False
		i += 1
	dp1 = [2]
	for jj in range(3, n + 1, 2):
		if dp[jj] == True:
			dp1.append(jj)
	return dp1
dp = sieve(2 * 10 ** 5)
arr = []
(n, m) = map(int, input().split())
for i in range(n):
	a = list(map(int, input().split()))
	arr.append(a)
uni_ans = 10 ** 5
for i in range(n):
	ans = 0
	for j in range(m):
		ele = arr[i][j]
		idx = b_s(dp, ele)
		ans += dp[idx] - ele
	uni_ans = min(ans, uni_ans)
for i in range(m):
	ans = 0
	for j in range(n):
		ele = arr[j][i]
		idx = b_s(dp, ele)
		ans += dp[idx] - ele
	uni_ans = min(ans, uni_ans)
print(uni_ans)


enter = input().split(' ')
rows = int(enter[0])
columns = int(enter[1])
matrix = []
minMove = 100000

def is_prime(n: int):
	if n <= 3:
		return n > 1
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i ** 2 <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i += 6
	return True
d = {}
for i in range(rows):
	matrix.append([])
	c = input().split(' ')
	totalMoves = 0
	for a in range(columns):
		move = 0
		change = int(c[a])
		while not is_prime(change):
			change += 1
			move += 1
		matrix[i].append(move)
		totalMoves += move
		if a not in d.keys():
			d[a] = 0
		d[a] += move
	if totalMoves < minMove:
		minMove = totalMoves
minColumns = min(d.values())
if minColumns < minMove:
	minMove = minColumns
print(minMove)


(n, m) = tuple(map(int, input().split()))
pro = [list(map(int, input().split())) for _ in range(n)]
r = [0] * (10 ** 5 + 4)
r[1] = 1
for i in range(2, 10 ** 5 + 4):
	if r[i] == 0:
		j = 2
		while i * j < 10 ** 5 + 4:
			r[i * j] = 1
			j += 1
r[-1] = len(r) - 1
for i in range(10 ** 5 + 2, 0, -1):
	if r[i] == 1:
		r[i] = r[i + 1]
	else:
		r[i] = i
ren = [0] * n
col = [0] * m
for i in range(n):
	for j in range(m):
		ren[i] += r[pro[i][j]] - pro[i][j]
		col[j] += r[pro[i][j]] - pro[i][j]
print(min(ren + col))


(m, n) = map(int, input().split(' '))
X = list(zip(*[map(int, input().split()) for i in [True] * m]))
from bisect import bisect_left as bsl
MaxPrime = 100004

def vec_primes(n):
	sieve = [True] * (n // 2)
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i // 2]:
			sieve[i * i // 2::i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [2 * i + 1 for i in range(1, n // 2) if sieve[i]]
VecP = vec_primes(MaxPrime)
sum2P = [VecP[bsl(VecP, i)] - i for i in range(1, 10 ** 5 + 1)]
XT = [[sum2P[j - 1] for j in k] for k in X]
minCol = min(map(sum, XT))
minRow = min(map(sum, zip(*XT)))
print(min(minCol, minRow))


def ints():
	return list(map(int, input().split()))

def soe(n):
	prime = [1] * (n + 1)
	p = 2
	while p * p <= n:
		if prime[p] == 1:
			for i in range(p * 2, n + 1, p):
				prime[i] = 0
		p += 1
	return prime
p = soe(100500)
p[0] = -1
p[1] = 0
(n, m) = ints()
l = []
for _ in range(n):
	l.append(ints())
mm = []
for _ in range(n):
	mm.append([0] * m)
for i in range(n):
	for j in range(m):
		if p[l[i][j]] == 1:
			mm[i][j] = 0
			continue
		q = p[l[i][j]:min(l[i][j] + 200, len(p))].index(1)
		mm[i][j] = q
ans = 10 ** 9
for i in range(n):
	ans = min(ans, sum(mm[i]))
for j in range(m):
	count = 0
	for i in range(n):
		count += mm[i][j]
	ans = min(ans, count)
print(ans)


size = 10 ** 6
n = size
primos = [1] * (n + 1)
for i in range(2, n + 1):
	if primos[i] == 1:
		for j in range(i * i, n + 1, i):
			primos[j] = 0
primos[1] = 0
(n, m) = map(int, input().split())
ar = []
for i in range(n):
	ar.append(list(map(int, input().split())))
res = size
lstPrimos = [0] * size
lstPrimo = size - 1
while not primos[lstPrimo]:
	lstPrimo -= 1
for i in range(lstPrimo, 0, -1):
	if primos[i]:
		lstPrimo = i
	lstPrimos[i] = lstPrimo
for i in range(0, n):
	qtd = 0
	for j in range(0, m):
		k = ar[i][j]
		qtd += lstPrimos[k] - k
	res = min(res, qtd)
for j in range(0, m):
	qtd = 0
	for i in range(0, n):
		k = ar[i][j]
		qtd += lstPrimos[k] - k
	res = min(res, qtd)
print(res)


def sieve(mx):
	a = [0] * (mx + 1)
	a[0] = a[1] = 1
	for (i, e) in enumerate(a):
		if e == 0:
			for n in range(i * i, mx + 1, i):
				a[n] = 1
	return a
p = sieve(10 ** 5 + 100)
for i in range(10 ** 5 + 99, 0, -1):
	p[i] *= p[i + 1] + 1
(n, m) = map(int, input().split())
cols = [0] * m
mm = 10 ** 7
for i in range(n):
	row = list(map(int, input().split()))
	row_sum = 0
	for (a, j) in enumerate(row):
		tt = p[j]
		row_sum += tt
		cols[a] += tt
	mm = min(mm, row_sum)
print(min(min(cols), mm))


import sys, math
isprime = [0] * 1000010
all_prime = [2]
next_prime = [0] * 1000010

def seive():
	isprime[1] = isprime[0] = 1
	limit = int(math.sqrt(1000010)) + 2
	for i in range(4, 1000010, 2):
		isprime[i] = 1
	for i in range(3, 1000010, 2):
		if not isprime[i]:
			all_prime.append(i)
			if i <= limit:
				for j in range(i * i, 1000010, i * 2):
					isprime[j] = 1
seive()
prime = 0
for i in range(1000000):
	next_prime[i] = all_prime[prime]
	if all_prime[prime] == i:
		prime += 1
(r, c) = map(int, input().split())
input_matrix = []
move = []
for i in range(r):
	temp = list(map(int, input().split()))
	input_matrix.append(temp)
for i in range(r):
	co = 0
	for j in range(c):
		co += next_prime[input_matrix[i][j]] - input_matrix[i][j]
	move.append(co)
for i in range(c):
	co = 0
	for j in range(r):
		co += next_prime[input_matrix[j][i]] - input_matrix[j][i]
	move.append(co)
print(min(move))


def gen_prime(n):
	num = [0 for i in range(n + 1)]
	num[2] = 1
	num[3] = 1
	for i in range(4, n + 1):
		isprime = True
		for j in range(2, int(i ** 0.5) + 1):
			if num[j]:
				if not i % j:
					isprime = False
					break
		if isprime:
			num[i] = 1
	prime = []
	for i in range(2, n + 1):
		if num[i]:
			prime.append(i)
	return prime
(n, m) = map(int, input().split())
prime = gen_prime(10 ** 5 + 100)

def closest(x):
	l = 0
	r = len(prime) - 1
	while l < r:
		mid = (l + r) // 2
		if prime[mid] == x:
			return prime[mid]
		elif prime[mid] > x:
			r = mid
		else:
			l = mid + 1
	return prime[l]
a = [0 for i in range(n)]
for i in range(n):
	a[i] = [int(i) for i in input().split()]
diff = [[0 for i in range(m)] for i in range(n)]
for i in range(n):
	for j in range(m):
		diff[i][j] = closest(a[i][j]) - a[i][j]
min_sum = 10 ** 5 * m
for i in range(n):
	temp = sum(diff[i])
	if temp < min_sum:
		min_sum = temp
total = min_sum
min_sum = 10 ** 5 * n
for i in range(m):
	temp = 0
	for j in range(n):
		temp += diff[j][i]
	if temp < min_sum:
		min_sum = temp
print(min(total, min_sum))


from math import ceil, sqrt

def prime():
	l = [0] * 100001
	n = 100001
	l[0] = 2
	l[1] = 2
	l[2] = 2
	l[n - 1] = 100003
	for i in range(n - 2, 2, -1):
		flag = True
		for j in range(2, ceil(sqrt(i) + 1)):
			if i % j == 0:
				flag = False
				break
		if flag:
			l[i] = i
		else:
			l[i] = l[i + 1]
	return l
pri = prime()
(n, m) = map(int, input().split())
mat = list()
for i in range(n):
	mat.append(list(map(int, input().split())))
near = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
	for j in range(m):
		near[i][j] = abs(mat[i][j] - pri[mat[i][j]])
k = float('inf')
for i in range(n):
	tmp = 0
	for j in range(m):
		tmp += near[i][j]
	k = min(tmp, k)
for i in range(m):
	tmp = 0
	for j in range(n):
		tmp += near[j][i]
	k = min(tmp, k)
print(k)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_primes(n):
	m = n + 1
	numbers = [True] * m
	for i in range(2, int(n ** 0.5 + 1)):
		if numbers[i]:
			for j in range(i * i, m, i):
				numbers[j] = False
	primes = []
	for i in range(2, m):
		if numbers[i]:
			primes.append(i)
	return primes
primes = get_primes(10 ** 6)
(n, m) = map(int, input().split())
dl = [0] * (10 ** 6 + 1)
dl[0] = 2
dl[1] = 1
for i in range(len(primes) - 1):
	(cur, next) = (primes[i], primes[i + 1])
	dl[cur] = 0
	for num in range(cur + 1, next):
		dl[num] = next - num
moves = 999999999999999999
cols = [[] for i in range(m)]
for _ in range(n):
	a = list(map(int, input().split()))
	mm = 0
	for j in range(m):
		i = a[j]
		cols[j].append(i)
		mm += dl[i]
	moves = min(moves, mm)
for each in cols:
	mn = 0
	for p in each:
		mn += dl[p]
	moves = min(moves, mn)
print(moves)


MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
from bisect import *
l = [1] * (10 ** 5 + 100)
for i in range(2, int((10 ** 5 + 100) ** 0.5) + 1):
	for j in range(i * i, 10 ** 5 + 100, i):
		l[j] = 0
lprime = [i for i in range(2, 10 ** 5 + 100) if l[i] == 1]
(n, m) = f()
l = []
for _ in range(n):
	l.append(il())
for i in range(n):
	for j in range(m):
		l[i][j] = lprime[bisect_left(lprime, l[i][j])] - l[i][j]
mn = 10 ** 9
for i in range(n):
	mn = min(mn, sum((j for j in l[i])))
for i in range(m):
	mn = min(mn, sum((l[j][i] for j in range(n))))
print(mn)


import math
from collections import defaultdict
import sys
primeCache = defaultdict(list)

def primeSieve(n):
	primes = []
	primeCache[1].append(1)
	primeCache[2].append(2)
	primes.append(2)
	for i in range(2, n):
		if i not in primeCache:
			primes.append(i)
			primeCache[i + i].append(i)
		if i in primeCache:
			lst = primeCache[i]
			for factor in lst:
				primeCache[i + factor].append(factor)
			del primeCache[i]
	return primes

def binarySearch(lst, k):
	l = 0
	r = len(lst) - 1
	while l < r:
		m = (l + r) // 2
		if lst[m] >= k:
			r = m
		else:
			l = m + 1
	return lst[r]

def solve(grid):
	primesList = primeSieve(100200)
	n = len(grid)
	m = len(grid[0])
	goalGrid = [[0 for _ in range(m)] for _ in range(n)]
	for i in range(n):
		for j in range(m):
			goalGrid[i][j] = binarySearch(primesList, grid[i][j]) - grid[i][j]
	minSum = math.inf
	for row in goalGrid:
		g = sum(row)
		if g < minSum:
			minSum = g
	for j in range(len(goalGrid[0])):
		partSum = 0
		for i in range(len(goalGrid)):
			partSum += goalGrid[i][j]
		if partSum < minSum:
			minSum = partSum
	return minSum

def readinput():
	(n, m) = map(int, sys.stdin.readline().rstrip().split(' '))
	lst = []
	for _ in range(n):
		row = list(map(int, sys.stdin.readline().rstrip().split(' ')))
		lst.append(row)
	print(solve(lst))
readinput()


max_value = 1000000
prime = [True for i in range(max_value + 1)]
prime[0] = prime[1] = False
p = 2
while p * p <= max_value:
	if prime[p]:
		for i in range(p * 2, max_value + 1, p):
			prime[i] = False
	p += 1
(row, col) = map(int, input().split())
matrix = []
for i in range(row):
	row_input = list(map(int, input().split()))
	matrix.append(row_input)
number_dict = {}
count_matrix = []
for r in range(row):
	count_row = []
	for c in range(col):
		number = matrix[r][c]
		if number not in number_dict:
			count = number
			while not prime[count]:
				count += 1
			number_dict[number] = count
		else:
			count = number_dict[number]
		count_row.append(count - number)
	count_matrix.append(count_row)
min_moves = 1000000
for r in range(row):
	row_sum = 0
	for c in range(col):
		row_sum += count_matrix[r][c]
	min_moves = min(min_moves, row_sum)
for c in range(col):
	col_sum = 0
	for r in range(row):
		col_sum += count_matrix[r][c]
	min_moves = min(min_moves, col_sum)
print(min_moves)


import sys
MAX_SIZE = 100001
isprime = [True] * MAX_SIZE
prime = []
SPF = [None] * MAX_SIZE
d = dict()

def manipulated_seive(N):
	isprime[0] = isprime[1] = False
	for i in range(2, N):
		if isprime[i] == True:
			prime.append(i)
			d.setdefault(i, 1)
			SPF[i] = i
		j = 0
		while j < len(prime) and i * prime[j] < N and (prime[j] <= SPF[i]):
			isprime[i * prime[j]] = False
			d.setdefault(i * prime[j], 0)
			SPF[i * prime[j]] = prime[j]
			j += 1
manipulated_seive(100001)
d.setdefault(1, 0)
prev = 100003
for i in range(100000, 0, -1):
	if d[i] == 0:
		d[i] = prev
	else:
		d[i] = i
		prev = i
ans = sys.maxsize
(n, m) = map(int, input().split())
l = []
for i in range(n):
	l.append(list(map(int, input().split())))
for i in range(n):
	c = 0
	for j in range(m):
		c += d[l[i][j]] - l[i][j]
	ans = min(c, ans)
for j in range(m):
	c = 0
	for i in range(n):
		c += d[l[i][j]] - l[i][j]
	ans = min(c, ans)
print(ans)


import sys
input = sys.stdin.readline
read = lambda : map(int, input().split())
read_float = lambda : map(float, input().split())

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // math.gcd(a, b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def next_prime(n, primes):
	while primes[n] != True:
		n += 1
	return n
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()

def binary_search(low, high, w, h, n):
	while low < high:
		mid = low + (high - low) // 2
		if check(mid, w, h, n):
			low = mid + 1
		else:
			high = mid
	return low

def check(l, ps, n, t):
	for i in range(n - l + 1):
		if ps[i + l] - ps[i] <= t:
			return True
	return False
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
import bisect as bis
import random
import sys

def solve():
	primes = sieve(10 ** 5 + 10 ** 2)
	ps = [0]
	nextprime = {}
	for i in range(10 ** 5 + 10):
		nextprime[i] = next_prime(i, primes)
	(n, m) = read()
	(c, r) = ([], [])
	matrix = [list(read()) for _ in range(n)]
	r = [0 for i in range(m)]
	for i in range(n):
		s = 0
		for j in range(m):
			s += nextprime[matrix[i][j]] - matrix[i][j]
			r[j] += nextprime[matrix[i][j]] - matrix[i][j]
		c.append(s)
	print(min(min(c), min(r)))
for _ in range(1):
	solve()


maxn = 150035
primos = [0 for x in range(maxn)]

def crivo():
	primos[1] = primos[0] = 1
	for i in range(2, maxn):
		if primos[i] == 0:
			for j in range(i + i, maxn, i):
				primos[j] = 1
	for i in range(maxn - 2, -1, -1):
		if primos[i] != 0:
			primos[i] += primos[i + 1]
crivo()
colunas = [0 for x in range(maxn)]
(n, m) = map(int, input().split())
res = 1000000000.0
for i in range(0, n):
	aux = 0
	linha = list(map(int, input().split()))
	for j in range(m):
		aux += primos[linha[j]]
		colunas[j] += primos[linha[j]]
	if i == n - 1:
		for j in range(m):
			res = min(colunas[j], res)
	res = min(aux, res)
print(res)