Description

小Y同学的GF小Z喜欢一种特殊的手链。这种手链由不同颜色的珠子串成，而且珠子颜色构成循环，循环次数>1。 七夕节快到了，小Y决定送一条小Z喜欢的手链给她。于是小Y去买了一条普通的手链，自己把它剪开，然后在首尾加入一些珠子使它变成小Z喜欢的那种特殊手链。不过小Y想尽量少加珠子，因为手链太长就不好了。 请你帮小Y计算一下他最少需要加多少颗珠子。（不能在剪开的手链中间加珠子）

这是一条由9颗珠子构成循环节，循环次数为2的特殊手链

Input

输入有多组数据。每组数据一行，一个由小写字母组成的字符串，表示剪开后的手链，长度不超过100000。每个字母表示一种颜色。

Output

每组数据输出一行，小Y需要加的最少的珠子数。

Sample

Input

aaa
abc

Output

0
3

Source: LGW