题目描述

在智亦珅泽教育的“数论与博弈”专题课上，小珅和小泽正在玩一个关于质数的棋盘游戏。

质数（又称素数）是指一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除。例如 2, 3, 5, 7, 11 都是质数。

现在，有一个 $n \times n$ 的棋盘，棋盘上一共放置了 $n \times n$ 个棋子。每个棋子都有一个初始价值 $v_{i,j}$，其中 $i$ 表示行号，$j$ 表示列号（行和列均从 1 开始编号）。

小珅可以进行若干次操作，每次操作可以选择棋盘上的一个位置 $(x, y)$，将该位置棋子的价值 $v_{x,y}$ 增加 1。

小珅的目标是：通过最少的操作次数，使得棋盘上存在至少一行或一列，这一行（或这一列）中所有棋子的价值都变成质数。

请你帮小珅计算：达到这个目标所需的最少操作次数。

输入格式

第一行，一个整数 $n$，表示棋盘的大小为 $n \times n$。

接下来 $n$ 行，每行 $n$ 个整数 $v_{i,1}, v_{i,2}, \dots, v_{i,n}$，表示第 $i$ 行每个棋子的初始价值。

输出格式

输出一行，一个整数，表示使某一行或某一列全部变为质数所需的最少操作次数。

3
5 8 3
1 7 9
9 2 6

3

5
41 71 17 67 50
79 10 23 67 101
70 29 71 97 61
53 70 3 80 79
61 71 47 37 30

0

数据规模与约定

• 对于 100% 的数据：
  • $1 \le n \le 500$
  • $0 \le v_{i,j} \le 4 \times 10^4$