Xét đồ thị gồm \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\) và có nhãn là một số nguyên dương \(a_i\).

Gọi \(GCD(x, y)\) là ước số chung lớn nhất của hai số \(x, y\). Cạnh giữa hai đỉnh \(i, j\) có trọng số \(123456 - GCD(a_i, a_j)\).

Yêu cầu: Tìm cây khung nhỏ nhất của đồ thị.

Input

• Dòng đầu chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

• Gồm một số nguyên duy nhất là tổng trọng số của cây khung nhỏ nhất tìm được.

Constraints

• \(a_i \le 10^5\).
• Subtask \(1\) (\(50\%\) số điểm): \(n \le 500\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 50000\).

Example

3 
10 20 30

246892

Nguồn: 3D'21