Cho dãy số nguyên dương \(a_1, a_2, \dots, a_n\). Một bộ ba phần tử của dãy được gọi là bộ ba số đẹp nếu thỏa mãn điều kiện: tồn tại ba số nguyên \(i, j\) và \(k\) (\(0 < i < j < k \le n\)) sao cho \(a_i \cdot a_j \cdot a_k\) chia hết cho \(5\).

Yêu cầu: Hãy đếm số lượng bộ ba chỉ số \((i, j, k)\) khác nhau thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(3 \le n \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).

Output

• Đưa ra một số nguyên là kết quả tìm được theo yêu cầu.

Example

5
1 10 5 12 6

9

Scoring

• Có \(50\%\) số điểm tương ứng số test của bài thỏa mãn điều kiện: \(n \le 500; a_i \le 10^3\).
• Có \(50\%\) số điểm còn lại tương ứng số test không có ràng buộc gì thêm.