Get Min Move

In one operation you choose a character and delete the nearest identical character to its left and the nearest identical character to its right; if one side has none, delete only on the other side. The chosen character itself stays. Find the minimum number of operations needed to reach the shortest possible string.

输入格式

One line containing a non-empty lowercase string of length 1..100000.

输出格式

Output one integer, the answer.

样例 1

输入：

adabacaea

输出：

2

样例 2

输入：

aaaa

输出：

2

样例 3

输入：

abc

输出：

0

样例说明

The examples give 2, 2 and 0 respectively. The original example mixes up indices 8/4; choosing original index 4 deletes 2 and 6 and gives adbacea.