Sample Input

5
3 10
aab
6 10
bbbaaa
6 10
aaaaab
3 10
bba
3 10
baa

Sample Output

3
1
1
3
3