String Distance

For two strings $S$ and $T$, you can do the following operation for arbitrary number of times: Select a string $S$ or $T$, insert or delete a character at any position. The distance between two strings $S$ and $T$ is defined as the minimum number of operations to make $S$ and $T$ equal.

You will be given two strings $A[1..n],B[1..m]$ and $q$ queries.

In each query, you will be given two integers $l_i$ and $r_i$ ($1\leq l_i\leq r_i\leq n$), you need to find the distance between the continous substring $A[l_i..r_i]$ and the whole string $B$.

The first line of the input contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases.

For each case, the first line of the input contains a string $A$ consists of $n$ ($1\leq n\leq 100\,000$) lower-case English letters.

The second line of the input contains a string $B$ consists of $m$ ($1\leq m\leq 20$) lower-case English letters.

The third line of the input contains a single integer $q$ ($1\leq q\leq 100\,000$), denoting the number of queries.

Then in the following $q$ lines, there are two integers $l_i,r_i$ ($1\leq l_i\leq r_i\leq n$) in each line, denoting a query.

For each query, print a single line containing an integer, denoting the answer.

1
qaqaqwqaqaq
qaqwqaq
3
1 7
2 8
3 9

4
2
0

2020 Multi-University Training Contest 2