input:

24
100 10000
ab
babbab
baabbbb
abbababbb
bb
bbbaaaba
b
aababaa
aaabbb
abbabbaaa
aaaab
bbab
bbabb
baaa
bbabbaaba
abaa
b
aabbbb
babbbbbb
bbaaba
aba
bbb
abbbaabaa
aa
bbaabaabbb
abbbbbb
aabbbaabba
ababba
aabbaab
ababa
aabbabbaab
b
aabaabaab
baaababa
babaaa
abaaaabbbb
aaaaabaa
bbb
bbab
baaa
bbabba
ababbb...

output:

2
3
6
11
4
5
3
5
6
8
5
4
4
3
4
2
3
6
10
4
2
5
6
2
8
9
5
7
4
2
7
3
3
6
3
8
6
5
4
3
4
8
3
4
7
2
2
3
9
7
2
2
7
11
3
5
5
8
3
6
6
3
5
4
4
8
4
2
5
8
3
5
5
4
5
3
2
5
3
10
4
5
5
9
4
4
7
3
5
3
5
9
4
4
3
7
8
6
5
3
3
3
6
11
7
8
3
5
6
8
5
7
7
3
7
3
3
6
13
7
3
8
6
3
8
9
5
7
4
3
7
3
3
6
3
8
6
8
7
3
7
8
3
4
10
3
3...

result:

ok 600000 lines