题目描述

Polycarp 喜欢能被 $3$ 整除的数字。

他有一个很大的数字 $s$。Polycarp 想要从中切割出尽可能多的能被 $3$ 整除的数字。为此，他可以在任意相邻的两位数字之间进行任意次数的竖直切割。经过 $m$ 次这样的切割后，总共会得到 $m+1$ 个部分。Polycarp 会分析每一个得到的数字，并统计其中能被 $3$ 整除的数字的数量。

例如，如果原始数字是 $s=3121$，Polycarp 可以通过两次切割将其分成三部分：$3|1|21$。这样，他将得到两个能被 $3$ 整除的数字。

Polycarp 可以在任意一对相邻数字之间进行切割。切割后得到的数字不能有多余的前导零（也就是说，只有当数字本身就是单个字符 '0' 时，才可以以 $0$ 开头）。例如，007、01 和 00099 都不是合法的数字，但 90、0 和 10001 是合法的。

Polycarp 最多能切割出多少个能被 $3$ 整除的数字？

输入格式

输入的第一行包含一个正整数 $s$。数字 $s$ 的位数在 $1$ 到 $2 \cdot 10^5$ 之间（包含两端）。第一位（最左边）数字不为 $0$。

输出格式

输出 Polycarp 通过在给定数字 $s$ 上进行竖直切割，最多能得到多少个能被 $3$ 整除的数字。

输入输出样例 #1

输入 #1

3121

2

6

1

1000000000000000000000000000000000

33

201920181

4

说明/提示

在第一个样例中，一个最优切割方案为 $3|1|21$。

在第二个样例中，不需要进行任何切割。给定的数字 $6$ 本身就是一个能被 $3$ 整除的数字。

在第三个样例中，需要在每一对数字之间都进行切割。这样，Polycarp 得到一个数字 $1$ 和 $33$ 个数字 $0$。每个 $0$ 都是能被 $3$ 整除的数字。

在第四个样例中，一个最优切割方案为 $2|0|1|9|201|81$。数字 $0$、$9$、$201$ 和 $81$ 都能被 $3$ 整除。

由 ChatGPT 4.1 翻译