Задачи
Задача о сундуке
Задача о сундуке
Сундук по имени Вова, как и все другие сундуки, мечтает стать настоящим сейфом для своего хозяина. Для этого он хочет сделать себе необычный кодовый замок. Желающему его открыть будет предоставлена квадратная матрица размера \textbf{N}×\textbf{N}, заполненная случайными числами. Эти числа нужно сделать простыми, пользуясь только двумя операциями:
\begin{itemize}
\item увеличить число на \textbf{2}
\item уменьшить число на \textbf{1}
\end{itemize}
Напомним, что число называется \textit{простым}, если оно больше единицы и не имеет других делителей, кроме единицы и самого себя.
В качестве ответа замок будет требовать ввести минимальное количество операций, которое необходимо совершить, чтобы привести матрицу к желаемому виду.
\InputFile
В первой строке задаётся размер матрицы \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1500}). Каждая из следующих \textbf{n} строк содержит по \textbf{n} целых чисел. Это и есть сгенерированная замком матрица. Правда, она не совсем случайная. Известно, что каждый её элемент неотрицательный и не превышает \textbf{10^9}. Также, известно, что разница между её максимальным и минимальным элементами не превышает \textbf{10^6}.
\OutputFile
Число, после которого замок откроется.
Входные данные #1
3 3 4 9 8 7 10 2 5 6
Выходные данные #1
6