eolymp
bolt
Try our new interface for solving problems
Problems

The problem about the chest

The problem about the chest

Time limit 4 seconds
Memory limit 64 MiB

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. Who wants to open will be given a square matrix with N×N size, filled with random numbers. These numbers need to be made prime by using only two operations:

  • increase the number by 2

  • decrease the number by 1

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 be necessary to introduce the minimum number of operations that must be performed in order to transform the matrix to the desired form.

Input data

The first line contains the size of the matrix n (1n1500). Each of the next n lines contains n integers. This is matrix generated by the lock. To tell you 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.

Output data

Number, after which the lock will open.

Examples

Input example #1
3
3 4 9
8 7 10
2 5 6
Output example #1
6
Author Борис Соколов
Source Дистанционная Летняя Компьютерная Школа - лето 2013 года