题目描述

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

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

输入格式

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

输出格式

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

数据范围

对于 20% 的数据，1≤n≤10⁹；

对于 50% 的数据，1≤n≤10¹⁰⁰；

对于 70% 的数据，1≤n≤10¹⁰⁰⁰；

对于 100% 的数据，1≤n≤10¹⁰⁰⁰⁰⁰

样例数据

输入:

95764

输出:

6

说明:

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

输入:

1111

输出:

2

说明:

有两个111都是3的倍数