Trong số học, bội số chung nhỏ nhất (hay còn gọi tắt là bội chung nhỏ nhất, được viết tắt là BCNN, tiếng Anh: least common multiple hoặc lowest common multiple ~(LCM)~ hoặc smallest common multiple) của hai số nguyên a và b là số nguyên dương nhỏ nhất chia hết cho cả a và b (Kí hiệu là ~lcm(a, b)~).

Yêu cầu

Cho dãy số nguyên dương ~a~ gồm ~n~ phần tử ~a_1, a_2, a_3, ..., a_n~. Hãy đếm số cặp chỉ số ~(i, j)~ sao cho:

• ~1 \le i \le j \le n~
• ~a_i + a_j = 2 * lcm(a_i, a_j)~

Input

• Dòng đầu tiên gồm số nguyên ~n (1 \le n \le 10^6)~ - số phần tử của dãy a,
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ... , a_n (1 \le a_i \le 10^9)~.

Output

• Một dòng duy nhất là yêu cầu của bài toán

Scoring

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

Ví dụ

Input

6
1 2 1 3 4 3

Output

2