Cho một danh sách ~n~ số nguyên dương.

Nhiệm vụ của bạn là đếm số cặp số nguyên nguyên tố cùng nhau (Tức là ~UCLN~ của chúng là ~1~).

Input

• Dòng đầu tiên chứa số nguyên ~n~: Số lượng phần tử ~(1 \le n \le 10^5)~
• Dòng tiếp theo chứa ~n~ số nguyên ~x_1, x_2, x_3, x_4,..., x_n~ ~(1 \le x_i \le 10^6)~

Output

• Một dòng duy nhất là kết quả cần tìm

Scoring

• Không có giới hạn gì thêm

Ví dụ

Sample Input

8
5 4 20 1 16 17 5 15

Sample Output

19