The problem about the chest#4354
Chest named Vova, like all the other chests, dreams of becoming a real safe for his owner. To do this, he wants to make an unusual combination lock. Whoever wants to open it will be given an N \times N square matrix, filled with random numbers. These numbers need to be made prime by using only two operations:
increase the number by
decrease the number by
Recall that a number is called prime if it is greater than one and has no divisors other than one and itself.
In response, the lock will require entering the minimum number of operations that must be performed in order to transform the matrix to the desired form.
The first line contains the size of the matrix (1 \leq n \leq 1500). Each of the next lines contains integers. This is the matrix generated by the lock. To tell the truth, elements are not entirely random. It is known that each element is non-negative and not greater than 10^9. Also, it is known that the difference between the maximum and the minimum of its elements does not exceed 10^6.
The number after which the lock will open.
Example 1