Cho một dãy số nguyên không âm \(A = (a_1, a_2, ..., a_n)\). Đếm số cặp \((i, j)\) thoả mãn:

• \(1 \le i < j \le n\)
• \(a_i \times a_j\) là số chính phương

Một số nguyên không âm \(a\) được gọi là số chính phương nếu tồn tại số nguyên không âm \(b\) sao cho \(a = b^2\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(2 \le n \le 2\cdot 10^5\)) - số phần tử của dãy \(A\).
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2, ..., a_n\) (\(0 \le a_i \le 2\cdot 10^5\)) - các phần tử của dãy \(A\).

Output

• In ra số cặp \((i, j)\) thoả mãn tìm được.

Example

5
0 3 2 8 12

6

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 2000\)
• Subtask \(2\) (\(50\%\) số điểm): Không có giới hạn gì thêm