Trong giờ học, Tèo được biết đến tới khái niệm xâu đối xứng. Một xâu đối xứng là một xâu khi đọc từ trái qua phải hay ngược lại đều như nhau. Nhưng vì định nghĩa quá nhàn đối với anh, Tèo quyết định sẽ xào nấu thêm một chút. Tèo định nghĩa một xâu ~t~ là đẹp nếu ~t~ là một xâu đối xứng và biểu diễn số của t chia hết cho 2, chia hết cho 3 và chia hết cho 5.

Ví dụ các xâu đẹp: ~01233210, 030, 0000~ (Có thể có các chữ số ~0~ thừa ở đầu xâu)

Cho một xâu kí tự ~s~ gồm các chữ số ~0~ đến ~9~. Hãy giúp tèo đếm có bao nhiêu cặp ~(l, r)~ ~(l \leq r)~ sao cho xâu ~s_l s_{l+1} ... s_r~ đẹp. Sau một hồi suy nghĩ thì Tèo nghĩ mình có thể nấu quá cháy nên không tìm được cách giải. Vì thế, anh nhờ bạn giải giúp bài toán siêu khó của Tèo này.

Input

• Gồm một dòng duy nhất chứa xâu kí tự ~s~ ~(|s| \leq 5 \cdot 10^3)~.

Output

• In ra kết quả của bài toán.

Sample Input

030

Sample Output

3

Note

Các cặp ~(l, r)~ thỏa mãn là ~(1, 1)~, ~(3, 3)~, ~(1, 3)~. Vì vậy, đáp án là ~3~.

Constraint