CodeCamp là hoạt động thường niên của IUH hằng năm dành cho các bạn trong đội tuyển Olympic Tin Học của trường. Trong các chuyến đi CodeCamp, thầy Tình sẽ dắt các bạn trong đội tuyển đến một vùng đất mới và riêng biệt để các bạn trong đội tuyển có thể tập trung toàn bộ thời gian của mình chỉ để học code và luyện code cùng nhau.

Năm 2023, đội tuyển đã được thầy Tình cho đi CodeCamp ở Đà Lạt. Trước khi xuất phát chuyến đi, thầy Tình yêu cầu ~N~ bạn thành viên trong đội tuyển chọn cho mình một con số yêu thích, và thầy Tình sẽ cho ~2~ bạn có cùng độ tương thích về con số yêu thích sẽ ngủ cùng 1 phòng và những ai không có độ tương thích với ai cả thì sẽ ngủ ở phòng lớn.

Cụ thể, ~N~ thành viên trong đội tuyển mỗi bạn sẽ có con số yêu thích là ~A_i~ (~ 1 \leq i \leq N ~). ~2~ bạn có chỉ số ~i~ và ~j~ sẽ có cùng độ tương thích khi và chỉ khi:

• ~1 \leq i < j \leq N~
• ~A_i + A_j = 2 * lcm(A_i, A_j)~ với ~lcm(A_i, A_j)~ là bội chung nhỏ nhất của ~A_i~ và ~A_j~

Là một trong các thành viên của đội tuyển Olympic Tin Học IUH, bạn hãy giúp thầy Tình đếm trong ~N~ thành viên sẽ có bao nhiêu cặp có cùng độ tương thích nhé.

Input

Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^5~) là số lượng thành viên trong đội tuyển.

Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, A_3,... A_N~ (~1 \leq A_i \leq 10^9~) tương ứng với con số yêu thích của thành viên thứ ~i~.

Output

Xuất ra một số nguyên duy nhất là số lượng cặp các bạn sinh viên có cùng độ tương thích.

Sample Input

6
2 3 3 5 7 19022024

Sample Output

1

SubTask

• SubTask 1 (50 điểm): với ~N \leq 100~ và ~A_i \leq 100~.
• SubTask 2 (50 điểm): không có giới hạn gì thêm.