Trong lớp học toán ngày hôm nay của Cirno, cô ra một bài toán cho các học sinh của mình:

Cho một số nguyên dương, hãy đếm số cách xóa bỏ một chữ số (số còn lại có thể có số 0 ở đầu) để số còn lại chia hết cho 3, nhưng không chia hết cho 9 (vì cô không thích số 9).

Input:

• Một số nguyên dương ~n \le 10^{100000}~.

Output

• Số cách xóa thỏa mãn.

Sample Test

Input:

396

Output:

2

Giới hạn

• 60% số điểm: ~n \le 10^{1000}~
• 40% số điểm: Không có giới hạn gì thêm.