题目内容

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

$abc$ 可以变成 $\begin{bmatrix} a & b & c \end{bmatrix}$ 也可以变成 $\begin{bmatrix} a \\ b\\ c \end{bmatrix}$ .

你需要保证$x * y = n$ .

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

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

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

输入描述

第一行输入一个正整数$n$，代表字符串的长度。

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

$1 \leq n \leq 10^4$

输出描述

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

样例

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

输入

8
abaababa

输出

3

说明

转换成$4*2$ 的矩阵:

$ab$

$aa$

$ba$

$ba$

共有$3$个连通块，$1$个$a$ 和$2$个$b$。