Cho \(n\) số tự nhiên \(a_1,a_2,…,a_n\). Tính tổng của tất cả \(GCD(a_i,a_j)\) với \(1 ≤ i < j ≤ n)\).

Input

• Dòng 1 chứa số nguyên \(n\) (\(1 ≤ n ≤ 2* 10^5)\).

• Dòng 2 chứa \(n\) số nguyên \(a_1,a_2,…,a_n (1 ≤ a_i ≤ 2*10^5)\).

Output

• Ghi một số là tổng của tất cả \(GCD(a_i,a_j)\) với \(1 ≤ i < j ≤ n)\).

Giới hạn:

• Subtask 1: \(1 ≤ n ≤ 1000\)

• Subtask 2: \(1 ≤ n ≤ 8000,1 ≤ a_i ≤ 1000\)

• Subtask 3: Không có thêm ràng buộc nào cả.

Sample Input

5
2 7 8 9 7

Sample Output

17