题目描述

给出字符串 $S$，请你删除尽量少的字符，使得剩下的字符串能写成 $AA$ 的形式。

输入格式

一行一个字符串 $S$，仅包含小写字母。$(1\le |S|\le 5200)$

输出格式

输出最少删除的字符数。

样例

输入

ababa

输出

1