Перед Вами матрица размера n × m, состоящая из целых чисел. За один ход разрешается применить к матрице единственное преобразование: выбрать произвольный элемент матрицы и увеличить его на 1. Каждый элемент можно увеличивать произвольное количество раз.
Вас очень интересуют простые числа. Напомним, что простым числом называется целое положительное число, которое имеет ровно два различных целых положительных делителя: единицу и само себя. Например, числа 2, 3, 5 — простые, а числа 1, 4, 6 — нет.
Вы считаете матрицу простой, если выполняется хотя бы одно из следующих двух условий:
- существует строка матрицы, в которой все числа простые;
- существует столбец матрицы, в котором все числа простые;
Ваша задача — посчитайте, за какое минимальное количество ходов можно получить из имеющейся матрицы простую матрицу.
Выходные данные
Выведите единственное целое число — минимальное количество ходов, которое потребуется, чтобы из заданной матрицы получить простую матрицу. Если заданная матрица — простая, выведите 0.
Примечание
В первом примере нужно один раз увеличить число 1 в клетке (1, 1). Таким образом, первая строка будет состоять из простых чисел: 2, 2, 3.
Во втором примере нужно три раза увеличить число 8 в клетке (1, 2). Таким образом, второй столбец будет состоять из простых чисел: 11, 2.
В третьем примере ничего делать не нужно, поскольку второй столбец уже состоит из простых чисел: 3, 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 3
5 6 1
4 4 1
|
1
|
|
2
|
2 3
4 8 8
9 2 9
|
3
|
|
3
|
2 2
1 3
4 2
|
0
|