思路：枚举+BFS

首先看这个数据范围，可以知道的是一个数的因子数不会太大。暴力枚举可以发现，10000以内因子数最大的数是 $9240$ ，共有 $64$ 个因子。

所以可以枚举因子来确定矩阵的行数和列数。即枚举$x*y=n$ 中的$x$ , 然后$y = n / x$

接着根据结果构造出新矩阵，在新矩阵上进行BFS求连通块。

这样最多跑 $64$ 次 $BFS$ 求连通块。

题目内容

给定一个长度为$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$。