Một ngày rảnh rỗi, Nam chơi trò chơi với những con số. Nam lấy một số tự nhiên ~N~ rồi thực hiện biến đổi thành số mới. Với mỗi cách biến đổi Nam xóa đi một số chữ số liên tiếp của ~N~ (nhưng không xóa hết) Nam nhận được một số mới, nếu số ~N~ được chia thành ~2~ phần thì số mới được ghép từ hai phần này và giữ nguyên thứ tự.

Yêu cầu: Hãy đếm các cách biến đổi như trên để số ~N~ mới sau khi biến đổi chia hết cho ~3~.

Lưu ý: Thao tác xóa tại hai vị trí khác nhau sẽ tạo ra hai cách biến đổi khác nhau. Số ~N~ giữ nguyên được coi là một cách biến đổi.

Input

Một dòng duy nhất là số nguyên ~N~ ~(1 \le |N| \le 10^5~, ~|N|~ số lượng chữ số của ~N~ ~)~

Output

In ra số cách xoá tìm được

Subtask

• Subtask 1: Có ~50\%~ số test có số các chữ số của ~N \le 300~
• Subtask 2: Có ~25\%~ số test có số các chữ số của ~N \le 10 ^ 4~
• Subtask 3: Có ~25\%~ số test có số các chữ số của ~N \le 10 ^ 5~

Sample Input 1

2001

Sample Output 1

4

Sample Input 2

160300

Sample Output 2

5

Giải thích

• Trong test 1: Các số mới là: ~2001; 201; 201; 21~

• Trong test 2: Các số mới là: ~60300; 0300; 300; 00; 0~