1s/128MB

题目描述

有一个奇怪的魔术师在变奇怪的魔术。魔术的内容是这样的：魔术师可以把任何东西变成原来的两倍——更神奇的是，增加的那部分是反的。但是这个魔术只对可爱的英文字母有用。比如一个字符串 AB，魔术师对它变完魔术后它就变成了ABBA。魔术师经过了多次魔术后(可能为 0 次)得到了一个新的字符串，他向观众们抛出了一个问题：原串最短的长度是多少？

输入格式

只有一个字符串，由大写英文字母组成（字母数<=100000），表示魔术结束后的 串

输出格式

魔术原串的最短长度

输入输出样例 #1

输入 #1

ABBAABBA

输出 #1

2

输入输出样例 #2

输入 #2

NBAABN

输出 #2

3

说明/提示

数据范围

• 对于 30% 的测试数据：字母数<=100
• 对于 60%：字母数<=1000
• 对于 100%：字母数<=100000