题目描述

一个十进制正整数n，可以从n中截取很多种不同的子串，如果这个子串构成的数是3的倍数，这个字串称为三倍子串。

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

桐桐很厉害，她能马上求出答案，你也一起算算吧。

输入格式

单个整数：表示输入的数n。

输出格式

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

输入/输出例子1

95764

6

输入/输出例子2

1111

2

样例解释

【样例1解释】

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

【样例2解释】

有两个111都是3的倍数

【数据范围】

10%的数据，1<=n的位数<=19;

100%的数据，20<=n的位数<=10^7。