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\le i<j\le n\) và \(gcd(a_i,a_j)>1\) với 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\((1< 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