题目描述

国际细胞处理公司（ICPC）是一个世界领先的基因序列分析机构。基因序列是一段核苷酸序列，在本题中用一个仅由 $\texttt{A, G, C, T}$ 四个字母组成的字符串来表示，其中每个字母代表一个核苷酸分子（分别是腺嘌呤脱氧核苷酸 (Adenine)，胞嘧啶脱氧核苷酸 (Cytosine)，鸟嘌呤脱氧核苷酸 (Guanine)，胸腺嘧啶脱氧核苷酸 (Thymine)）。

ICPC 的重要发现之一是，通过一种叫做基因优化有机折叠（Genetically Optimized Organic Folding, GOOF）的操作，可以在保留基因序列中 ICPC 想要研究的许多特征的同时，将原基因序列转变为一个更简单的基因序列。

一个简单的 GOOF 操作如下所示。找到核苷酸序列中两个相邻核苷酸之间的一点，满足从这个点开始，向两边读取，一直取到离该点较近的字符串的一段，读取到的字符串相同。例如，在序列 $\texttt{ATTACC}$ 中，有两个这样的点：$\texttt{AT-TACC}$ 和 $\texttt{ATTAC-C}$。然后选择其中一个点（比如第一个），然后沿这个点将这段基因序列折叠起来，合并相同的核苷酸（因此，在这个例子中 $\texttt{AT}$ 和 $\texttt{TA}$ 会合并起来，得到的序列可能是 $\texttt{CCAT}$ 或 $\texttt{TACC}$）。

通过重复 GOOF 操作，一段核苷酸序列可以变得十分短。然而，手工找到恰当的折叠点十分耗时。ICPC 想让你写个程序自动化这个找折叠点的过程，输入一个核苷酸序列，找到经过折叠操作后能得到的最短核苷酸序列。

输入格式

输入包含一个字符串 $s$，表示要分析的核苷酸序列。这个字符串仅由 $\texttt{A, G, C, T}$ 四个字母组成。$s$ 的长度在 $1$ 到 $4\cdot 10^6$ 之间（包括两端）。

输出格式

输出经过零次或更多次 GOOF 操作后能得到的最短核苷酸序列的长度。

ATTACC

3

AAAAGAATTAA

5