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.