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.

Difficulty: interview

Starter code:

Solutions:
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(list(range(maxn))):
  if ar[i]: dst = 0
  d[i] = min(d[i], dst)
  dst += 1

n, m = list(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)



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))


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))))  


import bisect

from math import sqrt

maxn = int(1e5 + 50)
isprime = [1 for i in range(maxn+1)]

d =  [1E9 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)))




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))))


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 = list(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))


def __starting_point():
    main()


__starting_point()

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))))


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))


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)

#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)

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))

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()

#python3
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 (ll i = 2; i*i <= n+1; ++i) {
        if (isPrime[i]) {
            for (ll j = i * 2; j <= n; j += i)
                isPrime[j] = 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
    #--------------------------------INPUT---------------------------------
    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)
    #print(allprimes)
    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]))
    '''
    for i in range(n):
        for j in range(m):
            print(tostore[i][j], end=" ")
        print()
    ''' 
    
    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]
    #print(rowsum[:n])
    #print(colsum[:m])
    minone = min(min(rowsum[:n]),min(colsum[:m]))    
    output = minone
    #-------------------------------OUTPUT----------------------------------
    if os.path.exists('output.txt'):
        open('output.txt', 'w').writelines(str(output))
    else:
        sys.stdout.write(str(output))


def __starting_point():
    main()
#threading.Thread(target=main).start()

__starting_point()

import sys;

class MyReader:
#    file = null;
    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);



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 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 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))

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 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))))  





# Made By Mostafa_Khaled


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=list(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 
#print(req)
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)



# -*- coding: utf-8 -*-
# @Date    : 2019-02-08 08:18:25
# @Author  : raj lath (oorja.halt@gmail.com)
# @Link    : link
# @Version : 1.0.0

from sys import stdin

max_val=int(10e12)
min_val=int(-10e12)

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)

n, m = list(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))


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
# print(dp[:10])
n, m = list(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))


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

N = int(1e5+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))


nearest_prime=[0]*(int(1e5+1))
nearest_prime[0]=2
nearest_prime[1]=1
prime_bool=[0]*(int(1e5+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(1e5)+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(1e5),1,-1):
	if prime_bool[i]:
		nearest_prime[i]=0
		np=i
	else:
		nearest_prime[i]=np-i

#print(nearest_prime[:10])

ans=1e9
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]]
#	print("row",i,req)
	ans=min(ans,req)

for i in range(m):
	req=0
	for j in range(n):
		req+=nearest_prime[arr[j][i]]
#	print("col",i,req)
	ans=min(ans,req)

print(ans)


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):
    'Find leftmost item greater than or equal to 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:  
          
            # put i into prime[] vector  
            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 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))