Prime Matrix

题意翻译

给你一个n*m的矩阵,每个位置上有一个数,你每操作一次可以给其中一个数加上1,输出要使矩阵中至少有一行或者一列全都是质数要进行操作的最少次数. 贡献者：Fuko_Ibuki

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

3 3
1 2 3
5 6 1
4 4 1

输出样例 #1

1

输入样例 #2

2 3
4 8 8
9 2 9

输出样例 #2

3

输入样例 #3

2 2
1 3
4 2

输出样例 #3

0

说明

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.