当你到达戴高乐机场时，你天真地接受了一位未经授权的司机的搭乘，他向你提供了“优惠价格”。结果是一场灾难：不仅价格极其昂贵，而且司机为了证明这个价格的合理性，让行程比必要的长得多。

你之所以注意到这场骗局，是因为你多次经过同一个地方：事实上，你的记忆力非常好，以至于你可以清楚地记得你所走的路径，包括骗子强迫你走的每一个环路。

现在，你在警察局填写针对该司机的投诉，一名警官要求你讲述你的经历。她甚至要求你提供所走路径的所有细节。因为你不想再浪费几个小时来讲述这些，你决定提供一个压缩版本。

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

更准确地说，你需要编写一个程序，输入你经过的地点列表，并返回该路径的最短压缩形式的大小。这样的压缩路径可以是： 一个你经过的单一地点，称为“原子路径”； 两个压缩路径的拼接； * 一个压缩路径的重复，即 $(C)^n$，意味着你连续 $n$ 次经过了路径 $C$ 所描述的路径。

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

输入格式

输入包含两行： 第一行包含一个整数 $N$，表示路径的长度。 第二行包含路径，描述为一个长度为 $N$ 的字符串。每个位置由一个字母数字字符描述：数字（从 ‘0’ 到 ‘9’）、小写字母（从 ‘a’ 到 ‘z’）或大写字母（从 ‘A’ 到 ‘Z’）。

数据范围

$0 < N \leqslant 700$

输出格式

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

样例

输入格式 1

22
aaabaaabccdaaabaaabccd

输出格式 1

4

说明

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

输入格式 2

4
aaba

输出格式 2

3

说明

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