B. Простая матрица
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Перед Вами матрица размера n × m, состоящая из целых чисел. За один ход разрешается применить к матрице единственное преобразование: выбрать произвольный элемент матрицы и увеличить его на 1. Каждый элемент можно увеличивать произвольное количество раз.

Вас очень интересуют простые числа. Напомним, что простым числом называется целое положительное число, которое имеет ровно два различных целых положительных делителя: единицу и само себя. Например, числа 2, 3, 5 — простые, а числа 1, 4, 6 — нет.

Вы считаете матрицу простой, если выполняется хотя бы одно из следующих двух условий:

  • существует строка матрицы, в которой все числа простые;
  • существует столбец матрицы, в котором все числа простые;

Ваша задача — посчитайте, за какое минимальное количество ходов можно получить из имеющейся матрицы простую матрицу.

Входные данные

В первой строке заданы два целых числа n, m (1 ≤ n, m ≤ 500) — количество строк и столбцов в матрице соответственно.

В каждой из следующих n строк записано по m целых чисел — исходная матрица. Все элементы матрицы являются целыми положительными числами. Все числа в исходной матрице не превосходят 105.

Числа в строках разделяются одиночными пробелами.

Выходные данные

Выведите единственное целое число — минимальное количество ходов, которое потребуется, чтобы из заданной матрицы получить простую матрицу. Если заданная матрица — простая, выведите 0.

Примеры
Входные данные
3 3
1 2 3
5 6 1
4 4 1
Выходные данные
1
Входные данные
2 3
4 8 8
9 2 9
Выходные данные
3
Входные данные
2 2
1 3
4 2
Выходные данные
0
Примечание

В первом примере нужно один раз увеличить число 1 в клетке (1, 1). Таким образом, первая строка будет состоять из простых чисел: 2, 2, 3.

Во втором примере нужно три раза увеличить число 8 в клетке (1, 2). Таким образом, второй столбец будет состоять из простых чисел: 11, 2.

В третьем примере ничего делать не нужно, поскольку второй столбец уже состоит из простых чисел: 3, 2.