#include <bits/stdc++.h>
#define Fst first
#define Snd second
#define MP make_pair
#define ll long long
#define PII pair<int,int>
#define PIL pair<int,ll>
#define PLI pair<ll,int>
#define PLL pair<ll,ll>
#define PDD pair<double,double>
using namespace std;
int tac,n,m,q;
char str[100010];
string sA,sB;
int d[100010][22][22];
inline void Main()
{
    scanf("%s",str),sA=str,n=sA.size();
    scanf("%s",str),sB=str,m=sB.size();
    for (int i=0;i<n;i++)
        for (int j=0;j<=m;j++)
            for (int k=0;k<=m;k++) d[i][j][k]=-1e9;
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<=m;j++)
        {
            if (j<m && sA[i]==sB[j]) d[i][j+1][1]=i;
            if (i==n-1) continue;
            for (int k=0;k<=m;k++)
            {
                if (j<m) d[i][j+1][k]=max(d[i][j+1][k],d[i][j][k]);
                d[i+1][j][k]=max(d[i+1][j][k],d[i][j][k]);
                if (j<m && sA[i+1]==sB[j]) d[i+1][j+1][k+1]=max(d[i+1][j+1][k+1],d[i][j][k]);
            }
        }
    }
    scanf("%d",&q);
    while (q--)
    {
        int l,r; scanf("%d%d",&l,&r),l--,r--; int res=0;
        for (int i=0;i<=m;i++)
            for (int j=0;j<=m;j++) if (d[r][i][j]>=l) res=max(res,j);
        printf("%d\n",r-l+1-res+m-res);
    }
}
int main()
{
    scanf("%d",&tac);
    while (tac--) Main();
    return 0;
}