Số nguyên tố 11

Cho dãy \(a\) gồm \(n\) số nguyên được đánh chỉ số từ \(1\) đến \(n\). Hãy đếm số cách chọn ba chỉ số \(i\), \(j\) và \(k\) sao cho \(1 \leq i < j < k \leq n\) và \(a_{i} \times a_{j} \times a_{k}\) là số chính phương.

Nhắc lại, số chính phương là số tự nhiên có căn bậc hai là một số tự nhiên.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 5 \times 10^{3})\).

• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{6})\).

Output

• Một dòng duy nhất chứa một số nguyên là số lượng cách chọn thỏa mãn.

Example

5
3 1 3 9 4

4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 5 \times 10^{2}\).

• Subtask \(2\) (\(30\%\) số điểm): \(a_{i} \leq 10^{2}\).

• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.