(traothuong_vn.*)

Hội thi “Bé khỏe bắt chuột” do trường Vncat tổ chức thành công tốt đẹp, hội thi đã chọn ra được những thí sinh khỏe nhất, bắt được nhiều chuột nhất. Trường Vncat sẽ tiến hành trao thưởng cho các thí sinh, mỗi thí sinh tham gia hội thi được nhận một phần quà bao gồm hiện vật và một hộp kẹo từ nhà tài trợ.

Có \(n\) hộp kẹo đã được chuẩn bị sẵn, trong hộp thứ \(i\ (i = 1\ldots n)\) có \(a_{i}\) viên kẹo. Trường Vncat mong muốn số lượng viên kẹo trong trong mỗi hộp đều là số nguyên tố nên đã yêu cầu bổ sung thêm kẹo sao cho số lượng kẹo trong mỗi hộp là số nguyên tố.

Yêu cầu: Hãy cho biết tổng số kẹo ít nhất cần bổ sung vào các hộp kẹo?

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (n \leq 10^{6})\)

+ Dòng tiếp theo ghi lần lượt các số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (a_{i} \leq {2 \times 10}^{6},\ i = 1\ldots n)\)

Kết quả:

+ Ghi một số duy nhất cho biết kết quả bài toán.

Ví dụ:

Giải thích ví dụ: cần bổ sung 1 viên kẹo vào hộp thứ nhất (đang có 4 viên), hộp thứ hai có 2 viên kẹo là số nguyên tố nên không cần bổ sung, bổ sung 3 viên kẹo vào hộp thứ ba (đang có 8 viên). Vậy tổng số kẹo cần bổ sung là \(1 + 0 + 3 = 4\).

Ràng buộc:

+ Có 50% số test tương ứng 50% số điểm có \(n \leq 1000\);

+ Có 50% số test còn lại tương ứng 50% số điểm không có ràng buộc nào thêm.