Let’s write a trivial statement.
Hôm nay trên trường mẫu giáo, Bờm mới được học về các dấu hiệu chia hết. Bờm rất hứng thú và thích môn toán học. Vì thế, Bờm liên tục tìm tòi và giải các bài toán liên quan. Hôm nay, Bờm đọc được một số dài cực kì trong sách Toán lớp 3, cậu nghĩ ngợi và tự hỏi rằng, nếu cắt số này đi một ít kí tự liên tiếp đầu tiên và một ít kí tự liên tiếp sau cùng, thì số còn lại có chia hết cho 9 hay không ? Bờm thích những điều vĩ đại, vì thế, cậu muốn số còn lại phải là dài nhất có thể. Lưu ý rằng, Bờm có thể không cắt đi bất kì kí tự nào của số và số còn lại phải không chứa số 0 vô nghĩa (số 0 đứng đầu một số).
Dữ liệu vào
Dòng đầu tiên là một số nguyên dương n (n <= 105) là số kí tự trong số mà Bờm thấy.
Dòng tiếp theo là n số nguyên ai (ai <= 9) là kí tự thứ i trong số, a1 > 0.
Dữ liệu ra
Một số nguyên duy nhất là độ dài lớn nhất của số mà Bờm nhận được. Nếu không tồn tại số thỏa mãn hãy in ra 0.
Input
1
9
Output
1
Input
3
3 0 9
Output
1
Giải thích
Ở ví dụ đầu tiên, số Bờm nhận được là 9 và 9 đã chia hết cho 9 nên không cần xóa kí tự nào.
Ở ví dụ 2, số Bờm nhận được là 309, và số dài nhất chia hết cho 9 là 9 – có 1 chữ số. Lưu ý rằng, số 09 không hợp lệ vì chứa số 0 vô nghĩa.