Ngày 27 tháng 4 năm 1521, trên vùng biển Mactan.
"Nguồn nước ngọt dự trữ đã bị nhiễm khuẩn nghiêm trọng do âm mưu phá hoại của bè lũ nổi loạn. Magellan đã ra lệnh kiểm tra toàn bộ \(N\) thùng nước còn lại trong khoang tàu Victoria. Mỗi thùng \(i\) có dung tích \(A_i\) (lít).
Để ổn định quân tâm, ông chỉ chọn ra các bộ 3 thùng nước \((i, j, k)\) để cung cấp cho đội cận vệ. Tuy nhiên, lão hoa tiêu trưởng đã cảnh báo: 'Tổng dung tích phải đạt được sự cộng hưởng với các con số của thần biển'. Nói cách khác, \(A_i + A_j + A_k\) phải là một số chính phương hoàn hảo (\(S^2\)). Đám thủy thủ đang rình rập ngoài cửa, thời gian của chúng ta chỉ còn đúng 1 giây!"

SYSTEM REPORT

• Total barrels (\(N\)): \(3,000\)
• Capacity range (\(A_i\)): \(1 \le A_i \le 1,000,000\)
• Max possible sum: \(3,000,000\)
• Constraint: \(1 \le i < j < k \le N\)

Nhiệm vụ

• Hãy xác định tổng số lượng các bộ ba chỉ số \((i, j, k)\) thỏa mãn điều kiện \(A_i + A_j + A_k = S^2\) (với \(S \in \mathbb{N}\))

Input

• Dòng thứ nhất chứa một một số nguyên \(N\) (\(1 \le N \le 3000\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^6\)).

Output

• Một số nguyên duy nhất là số bộ \(3\) thỏa mãn.

Example

Scoring

• Subtask 1 (\(40\%\) số điểm): \(N \le 1000, A_i \le 10^5\)
• Subtask 2 (\(60\%\) số điểm): Không có ràng buộc nào thêm