#1351. ROAD - Xây dựng đường

Ở Vương quốc Byteland có thành phố đánh số . Thành phố chọn số nguyên dương làm biểu tượng của mình. Một điều ngạc nhiên là chi phí để xây dựng đường cao tốc nối trực tiếp giữa hai thành phố lại phụ thuộc vào con số biểu tượng của hai thành phố này. Cụ thể, chi phí để xây dựng cao tốc nối thành phố và thành phố là . Ở đây được định nghĩa là phần dư của phép chia cho .

Hãy tìm cách giúp nhà Vua xây dựng được hệ thống đường cao tốc sao cho chỉ với hệ thống này đã đảm bảo sự đi lại giữa hai thành phố bất kỳ. Tất nhiên nhà Vua muốn tổng chi phí để xây dựng toàn bộ hệ thống cao tốc phải là nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương ;
• dòng tiếp theo, dòng thứ ghi số nguyên dương .

Dữ liệu ra:

• Một số nguyên duy nhất - Chi phí nhỏ nhất tìm được.

Ví dụ:

Dữ liệu vào:

3
4
9
15

Dữ liệu ra:

4

Giới hạn:

• Subtask số điểm có ;
• Subtask số điểm.