You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

自从塔子哥收到过一封外太空邮件后，就对外星文化来了兴趣。塔子哥通过古典查询得知，有一种神奇的字符串，这种神奇的字符串满足以下条件：

对于一个神奇的字符串$T$，

1.$|T|\%3==0$

2、对于任意的下标$i,i \in (3x|x=0,1,...,n)$,存在$T_i==T_{i+1}==T_{i+2}$

(注:空串是神奇字符串)

今天塔子哥又收到了一封外星人邮件，这个邮件中有一个仅由小写字符构成的字符率$S$，下标从$0$到$|S|-1$，塔子哥可以删除$0$个或多个位置上的字符，使得剩下的字符所构成的新字符串$T$是一个神奇字符串

请问，塔子哥至少需要删除多少个字符才能达到目的。

输入描述

输入一行，表示字符串$s$

$(1<=|S|<=100,000)$

输出描述

一个整数，表示需要删除的字符数量

示例1

输入

aabca

输出

2

说明

删除$bc$后，剩下的字符形成$aaa$

示例2

输入

abcdefghijk

输出

11

说明

删除所有字符后，剩下一个空串