Description

科学家们最近发现了一个奇怪的基因包含现象。假设有两个基因序列 A 和 B ，若 A 中各碱基对的数量均不超过 B ，我们就说 A 包含于 B ，B 包含了 A 。现在，对于长度为 n 的基因序列串 S = S_0 S_1 ... S_{n - 1} ，我们定义 S 的包含指数为，将 S 切割成最多的后面子串包含前面子串的子串个数。也就是说，若把 S 切割为 k 个子串，B_0 = S_0 S_1 ... S_{i_0} , B_1 = S_{i_0 + 1} S_{i_0 + 2} ... S_{i_1} ... B_{k – 1} = S_{i_{k - 2} + 1} S_{i_{k - 2} + 2} ... S_{n - 1} ，且必须保证 B_j 包含于 B_{j + 1} 其中 0 <= j <= k - 2 。那么所有合法的切割方案中，k 的最大值就是基因序列 S 的包含指数。

不过你的任务并没有就此结束，最近科学家们又研究出了重组基因序列的技术，对于给定的基因序列，他们能将它完全拆散为单个的碱基对，并将他们重新排列。你的任务就是帮助科学家们计算出对于给定的基因序列串 S ，将它重排后，它的包含指数最大值。

Input

多组测试数据，处理到文件结束。每组数据占一行，包含一个长度不超过 1000000 的基因序列串。该串仅包含 A, G, C, T ，表示 DNA 双链上其中一条链的碱基序列。

Output

对于每组数据，输出一个答案，每组数据占一行。

Sample

Input

AAAA
AGCTT

Output

4
2

Source: YCC