题目描述

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

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

输入格式

单个整数：表示输入的数字 $n$

输出格式

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

样例 #1

样例输入 #1

95764

样例输出 #1

6

样例 #2

样例输入 #2

1111

样例输出 #2

2

提示

样例1：

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

样例2：

有两个$111都是3的倍数$

数据范围

对于20% 的数据，$1≤n≤10^9$；

对于50% 的数据，$1≤n≤10^{100}$ ；

对于70% 的数据，$1≤n≤10^{1000}$；

对于100% 的数据，$1≤n≤10^{100000}$