Problem2755--字符串枚举练习之 - 音乐谜题 (多用例)

2755: 字符串枚举练习之 - 音乐谜题 (多用例)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

这道题是2754的多用例版本
设想我们用 a b c d e f g来代表音乐中的7个音符
现在有一位音乐爱好者,名叫Vlad,他决定为自己录制一道歌曲,然而,Vlad在录音方面并不擅长,他每次只能恰好录制两个音符,所以,为了录制好一首用字符串s表示的歌曲,他需要录制很多次,然后将它们拼接起来,拼接时,要求,第一段的第2个音符与第2段的第一个音符必须相等,举例来说:
假设Vlad最终要录制的歌典是:abcd
那么,他要录制: ab bc cd 所以他需要录制3次
又如:假设他最终要录制的歌曲是:abab
那么,他最小可以录制两段:ab ba
因为他可以使用ab ba先拼接成 aba,然后再用aba 和ab拼接成 abab
现在给出长度不超过50的字符串,代表这道歌曲的音符,请打印出Vlad最少需要录制几次?
注意本题有多组用例

Input

第一行一个整数t,表示用例的数量,
每个用例由两行组成,第一行一个整数n,表示歌曲的音符总数,第二行一个长度为n的字符串,表示这首歌曲。

Sample Input Copy

5
4
abab
7
abacaba
6
aaaaaa
7
abcdefg
5
babdd

Sample Output Copy

2
4
1
6
4

Source/Category