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
9
-2
-2
-2
-2
-2
-2
-2
7
6
-2
7
7
5
7
7
-2
5
5
5
5
5
10
9
8
-2
9
-2
-2
10
7
-2
-2
-2
-2
-2
-1
-2
-2
-2
-2
-2
8
8
-2
-2
6
-2
-2
-2
-2
5
5
5
5
-2
-2
9
-2
9
-2
9
-2
-2
8
-2
8
5
7
5
5
6
5
7
3
7
3
3
7
8
7
7
7
-2
-2
-2
-2
-2
-2
8
4
7
4
3
3
3
6
3

result:

wrong answer 12th lines differ - expected: '7', found: '9'