Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Cho một ma trận kích thước M x N, mỗi phần tử trong ma trận là một số nguyên dương. Chúng ta có thể thực hiện một thao tác biến đổi trên ma trận như sau: chọn 1 phần tử bất kỳ và tăng nó lên 1 đơn vị, mỗi phần tử trong ma trận có thể tăng với một số lần không hạn chế.

Một ma trận được gọi là ma trận nguyên tố nếu thỏa mãn một trong 2 điều kiện sau:

• Hoặc ma trận có ít nhất 1 hàng chứa toàn bộ là số nguyên tố
• Hoặc ma trận có ít nhất 1 cột chứa toàn bộ là số nguyên tố.

Nhiệm vụ của bạn là đếm số thao tác biến đổi ít nhất để chuyển ma trận ban đầu sang ma trận nguyên tố.

Input

• Dòng đầu chứa hai số nguyên dương M và N (1 ≤ M, N ≤ 1000)
• M dòng tiếp theo, mỗi dòng chứa N số nguyên dương, các số nguyên dương có giá trị ≤ 10⁶.

Output

• Một dòng duy nhất là số thao tác biến đổi ít nhất cần thực hiện.

Example

Input:
2 3
4 8 8
9 2 9

Output:
3

Giải thích:
            Chọn phần tử tại vị trí (1,2) và tăng nó thêm 3 lần
* Ghi chú:
- 30% test có n,m ≤ 100 và các phần tử trong bảng ban đầu ≤ 103
- 30% test tiếp theo có n,m ≤ 500 và các phần tử trong bảng ≤ 106
- 40% test còn lại n, m ≤ 1000 và các phần tử trong bảng ≤ 106