题目描述

给你一个数字串 $S$，仅包含 $0\sim 9$ 的数字，下标从 1 开始。

定义一次操作为：任意选择 $S$ 中相邻的两个位置 $s_i,s_{i+1}$，将这两个位置删去，再在位置 $i$ 插入 $s_i+s_{i+1}$ 的值。

例如，$S={\color{red}19}0$，选择 $i=1$。$s_1=1,s_2=9$，$s_1+s_2=10$，最终 $S$ 变为 ${\color{red}10}0$。

再如，$S=1{\color{red}90}$，选择 $i=2$。$s_2=9,s_3=0$，$s_2+s_3=9$，最终 $S$ 变为 $1{\color{red}9}$。

不难发现，不停进行这个操作，$S$ 最终会变成只有一位。

求 $S$ 变为一位时，操作次数的最小值。

输入格式

输入仅一行，为 $S$。

输出格式

输出 $S$ 变为一位时，操作次数的最小值。

190

3

4238934902923482348912232323990342312

52

0

0

提示

对于 $190$，最优操作方法是

1. ${\color{red}19}0\to {\color{red}10}0$
2. ${\color{red}10}0\to {\color{red}1}0$
3. ${\color{red}10}\to {\color{red}1}$

对于 $30\%$ 的数据，$|S|\le 1$。

对于 $50\%$ 的数据，$|S|\le 2$。

对于 $65\%$ 的数据，$|S|\le 3$。

对于 $90\%$ 的数据，$|S|\le 5$。

对于 $95\%$ 的数据，$|S|\le 100$。

对于 $100\%$ 的数据，$|S|\le 10^6$。