题目描述

给定一个 $n \times n$ 的矩阵，其中第 $i$ 行、第 $j$ 列的元素的值为 $a_{i,j}$。小爱每次可以花费一点代价，将某个元素的值 $+1$ 。

请问，小爱最少花费多少点代价，才能使得某一行或某一列均为素数？

输入格式

输入第一行，一个正整数 $n$ 接下来 $n$ 行，每行 $n$ 个正整数，其中第 $i+1$ 行，第 $j$ 个元素表示 $a_{i,j}$

输出格式

输出共一个整数，表示最小代价

3
5 4 3
1 7 8
9 2 6

1

样例解释 1

花费一点代价把4改成5，第二列均为素数

数据范围

• 对于 $30\%$ 的数据， $1 \leq n \leq 10$
• 对于 $60\%$ 的数据， $1 \leq n \leq 10^2$，$1\leq a_{i,j} \leq 10^2$
• 对于 $100\%$ 的数据， $1 \leq n \leq 10^3$，$1\leq a_{i,j} \leq 10^5$