Đầu năm học, Ban quản lý Ký túc xá Đại học Công nghiệp Hà Nội khảo sát thói quen sinh hoạt của ~n~ sinh viên mới để xếp phòng. Kết quả khảo sát của sinh viên thứ ~i~ được mã hoá thành một số nguyên dương ~a_i~, gọi là mã thói quen.

Theo cách mã hoá này, hai sinh viên càng có nhiều thói quen giống nhau thì hai mã càng có ước chung lớn. Vì vậy độ tương thích của hai sinh viên ~i~ và ~j~ được định nghĩa là ước chung lớn nhất ~\gcd(a_i, a_j)~ của hai mã.

Để đánh giá mức độ "hợp nhau" của cả khoá, Ban quản lý muốn biết tổng độ tương thích của tất cả các cặp sinh viên.

Yêu cầu

Hãy tính

$$S \;=\; \sum_{1 \le i < j \le n} \gcd(a_i,\ a_j) .$$

Nếu ~n = 1~ thì không có cặp nào và ~S = 0~.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên dương ~n~;
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.

Kết quả ra

Ghi ra một số nguyên duy nhất là giá trị ~S~.

Ràng buộc

~1 \le n \le 2 \cdot 10^5~; ~1 \le a_i \le 10^6~.

• Subtask 1 (15% số điểm – test 01–05): ~n \le 3000~;
• Subtask 2 (20% số điểm – test 06–10): dãy có không quá ~1000~ giá trị phân biệt;
• Subtask 3 (20% số điểm – test 11–14): mọi ~a_i~ đều là số nguyên tố;
• Subtask 4 (45% số điểm – test 15–20): không có ràng buộc bổ sung.

Lưu ý: kết quả có thể lên tới khoảng ~2 \cdot 10^{16}~, vượt quá phạm vi kiểu số nguyên 32 bit.

Ví dụ

Dữ liệu vào mẫu 1

5
4 6 8 9 12

Kết quả ra mẫu 1

30

Giải thích

Độ tương thích của ~10~ cặp là: ~\gcd(4,6) = 2~, ~\gcd(4,8) = 4~, ~\gcd(4,9) = 1~, ~\gcd(4,12) = 4~, ~\gcd(6,8) = 2~, ~\gcd(6,9) = 3~, ~\gcd(6,12) = 6~, ~\gcd(8,9) = 1~, ~\gcd(8,12) = 4~, ~\gcd(9,12) = 3~. Tổng bằng ~30~.