Bạn được cho một dãy số nguyên dương \(A\) có \(N\) phần tử \(A_1, A_2, \dots, A_N\).

Một bộ ba số Pythago gồm ba số nguyên dương \(a\), \(b\), và \(c\) sao cho \(a^2 + b^2 = c^2\) hoặc \(a^2 + c^2 = b^2\) hoặc \(b^2 + c^2 = a^2\).

Yêu cầu: Hãy tìm số lượng bộ ba phần tử của dãy \(A\) là một bộ ba số Pythago.

Input

• Dòng đầu tiên, chứa một số nguyên dương \(N\) (\(N \le 10^6\)).
• Dòng thứ hai, chứa \(N\) số nguyên dương, \(A_1, A_2, A_3, \dots, A_N\) (\(A_i \le 1000\)).

Các dữ liệu trên cùng một dòng cách nhau bởi chính xác một dấu cách.

Output

• In ra màn hình, số lượng bộ số \((i, j, k)\) thỏa mãn \(1 \le i < j < k \le N\) và \((A_i, A_j, A_k)\) là một bộ ba số Pytago.

Example

7
6 3 5 10 4 5 8

3

Scoring

• \(25\%\) số test tương ứng với \(25\%\) điểm thỏa mãn \(N \le 100\).
• \(25\%\) số test khác tương ứng với \(25\%\) điểm thỏa mãn \(N \le 5000\).
• \(25\%\) số test khác tương ứng với \(25\%\) điểm thỏa mãn \(N \le 10^6\) và \(A_i \le 100\).
• \(25\%\) số test còn lại tương ứng với \(25\%\) điểm thỏa mãn \(N \le 10^6\) và \(A_i \le 1000\).