Một buổi chiều sau giờ học, An đi dạo qua công viên và bắt gặp hai bạn nhỏ đang chơi trò ghép số bằng những con bài hình vuông có ghi số trên đó. Một bạn giơ lên con bài có số ~12~, bạn còn lại giơ con bài có số ~45~. Cả hai tranh luận với nhau rằng nếu ghép hai số này lại thì số mới có đặc biệt gì không?

Lúc này, An liền nhớ đến bài học sáng nay. Cậu mỉm cười và ngồi xuống cùng các bạn, giải thích một các đầy hào hứng: "Nếu số ~12~ chia hết cho ~3~ và số ~45~ cũng chia hết cho ~3~, thì khi mình ghép hai số này lại, số mới cũng sẽ chia hết cho ~3~ đấy!"...

Cho dãy ~A~ gồm ~N~ số nguyên dương ~A_1, A_2, ..., A_N~. Có bao nhiêu cặp chỉ số ~(i, j)~ ~(1 \le i \le j \le N)~ sao cho khi ta thực hiện thao tác ghép hai số ~A_i, A_j~ (ghép số ~A_i~ sau ~A_j~), ta được một số mới chia hết cho ~3~?

Yêu cầu

Đếm số lượng cặp chỉ số ~(i, j)~ ~(1 \le i \le j \le N)~ thỏa mãn yêu cầu trên.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên dương ~N~ ~(2 \le N \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(A_i \le 10^{50},\ 1 \le i \le N)~.

Dữ liệu đầu ra

Gồm một dòng duy nhất là số lượng cặp ~(i, j)~ thỏa mãn yêu cầu.

Ràng buộc dữ liệu

• Có 60% số test ứng với 60% số điểm: ~2 \le N \le 10^3;\ A_{i} \le 10^5;\ 1 \le i \le N~.
• Có 20% số test ứng với 20% số điểm: ~10^3 < N \le 10^5;\ A_{i} \le 10^9;\ 1 \le i \le N~.
• Có 20% số test ứng với 20% số điểm: Không ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

7
123 4 5 7 10 3 2

OUTPUT

7

Giải thích: Có tổng cộng ~7~ cặp ~(i, j)~ thỏa mãn gồm: ~(1, 6)~, ~(2, 3)~, ~(2, 7)~, ~(3, 4)~, ~(3, 5)~, ~(4, 7)~, ~(5, 7)~.