小美拿到了一个长度为n的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有x行y列，必须保证x*y=n，即每y个字符换行，共x行）。

该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？

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

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

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

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

样例解释：

平铺为3*3的矩阵：aab abb abb 共有2个连通块，4个a和5个b。

字符串的顺序不能改变，只能换行！

1\leq n\leq10^4