Bạn được cung cấp một mảng gồm \(n\) số nguyên \(a_1, a_2, ..., a_n\).

Định nghĩa một hàm \(f(l, r)\) là số cặp \((i, j)\) sao cho \(l \le i \le j \le r\) và \(gcd(a_i, a_j) != 1\) (gcd là ước số chung lớn nhất).

Hãy tính tổng của \(f(l, r)\) trên tất cả các cặp \(l, r\) sao cho \(1 \le l \le r \le n\). Nếu tổng này lớn hơn \(10^{18}\), hãy in ra \(1\).

Định dạng đầu vào

• Dòng đầu tiên: Số nguyên n biểu thị số phần tử của mảng.
• Dòng thứ hai: \(n\) số nguyên cách nhau bởi dấu cách \(a_1, a_2, ..., a_n\).

Định dạng đầu ra

• Xuất ra tổng yêu cầu.

Ràng buộc

• \(1 \le n, a_i \le 100000\).

Input 1

3
2 4 6

Output 1

15