20612번 - String Distance 다국어

문제

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.

제한

힌트