input:

20
2 5
bacba
aabbc
3
0 3
1 4
1 2
2 5
aacba
cbbac
8
0 3
1 2
1 2
1 0
1 2
0 2
0 0
0 0
4 4
aaac
caab
babb
ccba
8
2 0
3 2
2 1
2 1
1 3
2 2
1 2
3 1
4 3
bbb
ccc
abc
caa
3
2 0
0 0
3 2
3 3
cba
abc
bac
4
0 1
0 1
1 0
1 1
4 4
bcab
caba
cbcb
abca
1
1 1
5 4
baba
caba
aacb
abcb
caab
1
4 2
2 3
cab
aac
5
0 0
0 2
0 1
...

output:

6
6
-2
8
8
8
8
8
8
8
8
7
7
7
7
-2
-2
-2
7
6
6
6
7
7
-2
7
9
10
4
4
4
4
4
8
8
8
-2
8
8
8
8
6
-2
-2
-2
-1
-1
-1
-2
-2
7
-2
-2
6
6
-2
6
6
6
6
6
-2
4
4
4
-2
-2
-2
8
-2
8
-2
-2
-2
8
8
-2
8
5
5
5
5
-2
5
-2
5
5
5
5
5
-2
-2
5
5
-2
7
-2
-2
-2
7
7
5
-2
5
-2
-2
-2
-2
5

result:

wrong answer 23rd lines differ - expected: '-1', found: '7'