Trong một vương quốc cổ đại, có ~n~ thành phố được đánh số từ ~1~ đến ~n~. Mỗi thành phố mang một "mật mã cổ" là một số nguyên dương ~a_i~, đại diện cho đặc trưng văn hóa và lịch sử riêng của thành phố đó.

Nhà vua muốn xây dựng một hệ thống đường đi để kết nối tất cả các thành phố lại với nhau, nhằm tăng cường giao thương và phát triển toàn vương quốc. Tuy nhiên, việc xây dựng đường giữa hai thành phố không đơn giản, vì chi phí phụ thuộc vào mức độ "tương đồng" giữa hai nơi.

Cụ thể:

• Mức độ tương đồng giữa hai thành phố được đo bằng ước số chung lớn nhất của hai mật mã, tức là ~\operatorname{GCD}(a_i,a_j)~.

• Chi phí xây dựng con đường nối giữa hai thành phố ~i~ và ~j~ được xác định bởi: ~123456-\operatorname{GCD}(a_i,a_j)~.

Điều này có nghĩa là:

• Hai thành phố càng có nhiều điểm chung (GCD lớn) thì càng dễ kết nối (chi phí thấp),

• Ngược lại, hai thành phố càng khác biệt thì chi phí xây dựng càng cao.

Yêu cầu: Nhà vua muốn chọn ra một hệ thống đường sao cho:

• Tất cả các thành phố đều được kết nối (trực tiếp hoặc gián tiếp),

• Tổng chi phí xây dựng là nhỏ nhất có thể.

Nhiệm vụ của bạn là tính tổng chi phí nhỏ nhất đó.

Input

• Dòng đầu chứa số nguyên ~n~ - số lượng thành phố.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(a_i \le 10^5)~.

Output

In ra một số duy nhất là tổng chi phí nhỏ nhất để kết nối tất cả các thành phố.

Scoring

Sample Input 1

3
10 20 30

Sample Output 1

246892