Cho dãy số nguyên dương ~A=(a_1,a_2,…,a_n)~.

Yêu cầu

Hãy cho biết có bao nhiêu cặp chỉ số ~(i,j)~ thỏa mãn ~( i < j)~ và ước số chung lớn nhất của ~a_i~ và ~a_j~ bằng 1.

Dữ liệu

• Dòng 1 chứa số nguyên dương ~n~ ~(n \leq 1000)~.
• Dòng 2 chứa ~n~ số nguyên dương ~a_1,a_2,…,a_n~ ~(a_i \le 10^9)~ cách nhau bởi dấu cách.

Kết quả

Một số nguyên duy nhất là số cặp chỉ số ~(i,j)~ thỏa mãn yêu cầu đặt ra.

Input

4
1 2 3 4

Output

5