题目描述

给定一个长度为$n$的字符串。你可以把他转换成一个大小为$x\times y$ 的矩形，例如:

$abc$ 可以变成

也可以变成

你需要保证$x \times y = n$ .

接着，我们定义一个矩阵的权值为这个矩阵的连通块数量。

我们定义，上下左右四个方向相邻的相同字符是连通的。

请在所有可能的矩阵种找到一个权值最小的矩阵，并输出权值。

输入描述

第一行输入一个正整数$n(1 \leq n \leq 10^4)$，代表字符串的长度。

第二行输入一个长度为$n$的、仅由小写字母组成的字符串。

输出描述

输出一个整数表示最小权值。

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

8
abaababa

输出

3

说明

转换成$4\times 2$ 的矩阵，共有三个连通块，如下图所示。