International Cell Processing Company (ICPC) 是基因序列分析领域的全球领导者。基因序列是一串核苷酸序列，在本题中，它由一个仅包含字母 A、C、G 和 T 的字符串表示，每个字母代表一个单一的核苷酸（分别为腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶）。

ICPC 的一项关键发现是，通过一种称为“基因优化有机折叠”（Genetically Optimized Organic Folding，简称 GOOF）的过程，他们可以将基因序列转化为更简单的序列，同时保留 ICPC 想要分析的序列的许多特性。

单次 GOOF 操作的过程如下：在核苷酸序列中两个相邻的核苷酸之间找到一个点，使得序列从该点开始向两个方向读取时，直到序列较近的一端为止，内容完全相同。例如，在序列 ATTACC 中，有两个这样的点：AT-TACC 和 ATTAC-C。然后选择其中一个点（比如第一个），在该点折叠基因序列，合并相同的核苷酸（在这种情况下，AT 和 TA 将被合并，得到的序列将是 CCAT 或 TACC）。

通过重复应用 GOOF，核苷酸序列有可能变得更短。然而，手动寻找合适的折叠点非常耗时。ICPC 希望你编写一个程序，能够自动完成寻找折叠点并进行选择的过程，从而使给定的输入序列能够得到尽可能短的基因序列。

输入格式

输入包含一个字符串 $s$，表示待分析的核苷酸序列。该字符串仅由字符 A、C、G 和 T 组成。$s$ 的长度在 $1$ 到 $4 \cdot 10^6$ 之间（包含边界）。

输出格式

输出通过零次或多次应用 GOOF 后，所能得到的序列的最小长度。

样例

样例输入 1

ATTACC

样例输出 1

3

样例输入 2

AAAAGAATTAA

样例输出 2

5