三倍子串

题目描述

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

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

输入描述

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

输出描述

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

数据范围

• 对于20%的数据，1≤n≤10^9；
• 对于50%的数据，1≤n≤10^100；
• 对于70%的数据，1≤n≤10^1000；
• 对于100%的数据，1≤n≤10^100000