|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|4 초||512 MB||0||0||0||0.000%|
For two strings $S$ and $T$, you can do the following operation an 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]$ and $B[1..m]$, and also $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 continuous substring $A[l_i..r_i]$ and the whole string $B$.
The first line contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case:
The first line contains a string $A$ which consists of $n$ ($1 \leq n \leq 100\,000$) lower-case English letters.
The second line contains a string $B$ which consists of $m$ ($1 \leq m \leq 20$) lower-case English letters.
The third line contains a single integer $q$ ($1 \leq q \leq 100\,000$) denoting the number of queries.
Each of the following $q$ lines contains two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq n$) describing 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