Bạn được cho một danh sách gồm ~n~ số nguyên dương. Nhiệm vụ của bạn là đếm số cặp ~(i, j)~ với ~i < j~ sao cho hai số ở vị trí đó nguyên tố cùng nhau tức là ~GCD(x_i, x_j)~ = 1

Đầu vào:

Dòng đầu tiên chứa một số nguyên ~n~: số lượng phần tử trong danh sách.

Dòng thứ hai chứa n số nguyên ~x_1,x_2,\dots,x_n~: các phần tử của danh sách.

Đầu ra:

In ra một số nguyên: số lượng cặp số nguyên tố cùng nhau trong danh sách.

Ràng buộc:

~1 \le n \le 10^5~

~1 \le x_i \le 10^6~

Ví dụ :

Input:

8
5 4 20 1 16 17 5 15

Output:

19