String Distance

Problem Description

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$.

Input

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.

Output

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

Sample Input

1
qaqaqwqaqaq
qaqwqaq
3
1 7
2 8
3 9

Sample Output

4
2
0

Source

2020 Multi-University Training Contest 2