Background

Special for beginners, ^_^

Description

键盘有很多布局，比如qwerty、dvorak、colemak等三种键盘布局。现在有一个1行9列的数字键盘，请你重新设计键盘布局，使得打字速度最快。 打字员每一个时间片可以进行如下三种操作： a按一下当前的数字键输入一个字符，b向左移动一个位置，c向右移动一个位置。 打字员的初始位置位于键盘最左边的字符，计算在各种键盘布局下的最小时间片数。

Format

Input

输入一个字符串，表示该打字员需要输入的数字字符串（长度不超过1e5，不含有数字0）。

Output

输出最优键盘布局下，输入整个数字字符串的最小时间片数。

Samples

78432579

20

Limitation

1s, 1024KiB for each test case.