Description

对于两个字符串X和Y(只包含26个大写字母),如果对于每个字母t有num[X,t] <= num[Y,t],那么我们说X包含于Y,其中num[X,t]表示字符串X中字母t的个数.

给你一个字符串S,现在让你把S切割为n段S1，S2，…,Sn (S1+S2+…+Sn=S), 并满足对于任意的1 <= i < n都有Si包含于S i+1.

求n的最大值.

Input

输入包含多组数据,每组数据包含独立一行字符串(长度为1~200)

Output

输出最大的n

Sample

Input

ABABAB
AAXAAAABX
ABBABBBBXZ

Output

3
4
2

Hint

请用scanf("%s")来读入，数据可能有空行

Source: superDD