说明

当你抵达戴高乐机场时，你天真地接受了一位无证司机提供的“有竞争力价格”的搭车前往巴黎。结果是一场灾难：不仅价格极高，而且司机为了让这个价格显得合理，让行程变得比必要长得多。

你注意到了这个骗局，因为你多次经过同一个地方：事实上，你的记忆力非常好，能够清楚地记住你走过的路径，包括那位骗子迫使你绕的每一个圈子。

现在，你在警察局报案投诉这位司机，一位警官要求你讲述你的经历。她甚至要求你提供你所走路径的所有细节。因为你不想再花几个小时做这件事，你决定给出一个压缩版本。

假设你记得你经过了地点 A, B, C, D, A, B, C, D。在这种情况下，你宁愿告诉警官“我走了两遍路径 ABCD”，而不是“我走了路径 ABCDABCD”。由于你的路径重复了相同的地点序列，这将显著缩短你的陈述，而不会遗漏任何细节。

更精确地说，你需要编写一个程序，输入为你经过的地点列表，并返回该路径最短压缩形式的大小。这样的压缩路径可以是以下之一：

• 一个你经过的单个地点，称为“原子路径”；
• 两个压缩路径的连接；
• 一个压缩路径的重复，即 $(C)^n$，表示你连续走了 $n$ 次由 $C$ 描述的路径。

压缩路径的大小定义为其中包含的原子路径的数量。

输入格式

输入包含两行：

• 第一行包含一个整数 $N$，表示路径的长度。
• 第二行包含路径，描述为一个长度为 $N$ 的字符串。每个地点由一个字母数字字符描述：可以是数字（从 '0' 到 '9'）、小写字母（从 'a' 到 'z'）或大写字母（从 'A' 到 'Z'）。

输出格式

输出应包含一行，内容为一个整数，表示最短压缩路径的大小。

22
aaabaaabccdaaabaaabccd

4

4
aaba

3

提示

样例解释 1

该路径的最短压缩形式是 $(((a)^3b)^2(c)^2d)^2$。其中包含的原子路径是 $a$、$b$、$c$ 和 $d$。因此，其大小为 4。

样例解释 2

该路径的最短压缩形式是 $(a)^2ba$。其中包含的原子路径是 $a$、$b$ 和 $a$。因此，其大小为 3。

数据范围

$0 < N \leq 700$

翻译由 DeepSeek 完成