Từ thời Trung cổ, Toruń đã nổi tiếng với món bánh gừng truyền thống. Cậu bé Nicolaus muốn mua \(n\) hộp bánh gừng tại cửa hàng yêu thích của mình. Tuy nhiên, cửa hàng có những quy định rất nghiêm ngặt: ban đầu, Nicolaus nhận \(n\) hộp đã có sẵn bánh, trong đó hộp thứ \(i\) chứa \(a_i\) chiếc. Sau đó, cậu có thể mua thêm bánh và cho vào một số hộp sao cho ước chung lớn nhất của số bánh trong tất cả các hộp bằng \(1\). Có thể chứng minh rằng điều này luôn thực hiện được.

Ước chung lớn nhất của nhiều số là số nguyên dương lớn nhất mà tất cả các số đó đều chia hết cho nó.

Hãy giúp Nicolaus tính tổng số bánh ít nhất cần thêm vào các hộp để ước chung lớn nhất của số bánh trong tất cả các hộp bằng \(1\).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\), là số hộp bánh.

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\), trong đó \(a_i\) là số bánh ban đầu trong hộp thứ \(i\).

Dữ liệu ra

In ra một dòng chứa một số nguyên là tổng số bánh ít nhất Nicolaus cần thêm vào các hộp. Nếu không cần thêm bánh mà ước chung lớn nhất của các số đã bằng \(1\), in ra \(0\).

Ràng buộc

• \(2\le n\le 10^6\).
• \(1\le a_i\le 10^7\) với mọi \(1\le i\le n\).

Phân nhóm

1. \(17\) điểm: \(n=2\).
2. \(34\) điểm: \(n\le 10\).
3. \(11\) điểm: \(n\le 1000\).
4. \(38\) điểm: không có ràng buộc bổ sung.

Ví dụ

3
90 84 140

2