Cho một mảng ~A~ gồm ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ~(A_i \le 10^6)~. Một cặp chỉ số ~(i,j)~ với ~1 \le i < j \le N~ ~(N \le 10^5)~ được gọi là "cặp chỉ số hoàn hảo" nếu tổng ~A_i + A_j~ có đúng ~3~ ước số nguyên dương.

Yêu cầu: Hãy đếm số lượng cặp chỉ số hoàn hảo ~(i,j)~ trong mảng ~A~.

Input

• Dòng ~1~: Chứa số nguyên dương ~N~ là số lượng phần tử của mảng;

• Dòng ~2~: Chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~, ngăn cách bởi khoảng trắng.

Output

Một số nguyên duy nhất là số lượng cặp chỉ số hoàn hảo tìm được.

Scoring

Sample Input 1

5
1 2 3 7 11

Sample Output 1

2

Notes

Các cặp chỉ số hoàn hảo ~(i,j)~ thỏa mãn:

• ~A_1 + A_3 = 1 + 3 = 4~ (có ~3~ ước: ~1, 2, 4~);

• ~A_2 + A_4 = 2 + 7 = 9~ (có ~3~ ước: ~1, 3, 9~).