Yêu cầu:

Cho dãy số nguyên \((a_1, a_2,..., a_n)\), hãy đếm số cặp \((i, j)\) thỏa mãn: \(1 ≤ i < j ≤ n\) và \(gcd(a_i, a_j ) > 1\)

gcd là phép lấy ước chung lớn nhất của hai số.

Dữ liệu:

• Dòng đầu tiên ghi số nguyên không âm \(n (0 < n ≤ 100)\),

• Dòng thứ 2 ghi \(n\) số nguyên dương kiểu 64 – bit.

Kết quả:

• In ra số lượng cặp \((i, j)\) thỏa mãn yêu cầu.

Input

3
21 6 57

Output

3