Description

给定一个十进制正整数n，请问可以从n中截取多少种不同的子串，使得子串构成的数字是3的倍数。

例如：当n=1234时，有且仅有3，12，123，234这四个子串是3的倍数。

Input Format

单个整数：表示输入的数字n, 1<=n<=1000000000

Output Format

单个整数：表示3的倍数的子串数量。

95764

6

1111

2

Hint

样例1

子串6,9,57,576,957,9576是3的倍数

样例2

有两个111都是3的倍数

Source