Cho số tự nhiên ~N~. Bằng cách giữ nguyên hoặc xoá đi một số chữ số liên tiếp của ~N~ (nhưng không xoá hết) ta nhận được một số mới, nếu số ~N~ bị chia thành ~2~ phần thì số mới được ghép lại từ hai phần này và giữ nguyên trật tự.

Yêu cầu: Hãy xác định tất cả số cách xoá như trên để số ~N~ mới sau khi xoá chia hết cho ~3~. Lưu ý là hai vị trí khác nhau sẽ tạo ra hai cách xoá khác nhau. Số ~N~ giữ nguyên cũng được coi là một cách xoá.

Input

Đọc từ tệp CAU3.INP chứa số nguyên dương ~N~ (không quá ~10^5~ chữ số)

Output

Ghi ra tệp CAU3.OUT một số nguyên là số cách xoá tìm được

Scoring

Sample Input 1

1005

Sample Output 1

4

Sample Input 2

2009

Sample Output 2

3