Cho số nguyên dương \(n\) và dãy số nguyên dương \(a_1,a_2,…,a_n.\)

Yêu cầu: Đếm xem trong dãy có bao nhiêu cặp chỉ số \((i,j) (1≤i<j≤n)\) sao cho \(a_i+a_j \) là một số chính phương.

Input

• Dòng đầu tiên chứa số nguyên dương \(n (1≤n≤1000).\)

• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,…,a_n (1≤a_i≤10^6 ).\)

Output

• Một số nguyên duy nhất — là số lượng cặp \((i,j)\) sao cho \(a_i+a_j\) là số chính phương.

Ràng buộc

• Subtask 1 (50% số điểm): \(1≤a_i≤10^3\)

• Subtask 2 (50% số điểm): \(1≤a_i≤10^6.\)

Sample Input

4
1 3 6 2

sample Output

2