Description

给定一个字符串和一个K，将字符串分成若干个K长度的子串，从左到右依次划分，保证字符串长度为K的整数倍
将子串可以随意重新排列，使排列前后的所有子串拼接之后，连续的段最小，其中段是指在拼接后串中的一段连续的字母

Format

Input

第一行为一个整数K，第二行为字符串

Output

输出最小段数

Sample 1

Input

3
baabcbaca

Output

4

Limitation

1s, 1024KiB for each test case.
1≤T≤100
1≤k,∣s∣≤1000

Hint

样例1中可以将字符串分割成baa bcb aca ，经过重新排列，变成了aab bbc caa,重新拼接之后为aabbbccaa，共有aa bbb cc aa最少四段

Source

Vijos Original