#include <bits/stdc++.h>
#define ll long long
//#define int long long
using namespace std;

void upd(int &a,const int &b){ if(a==-1||a>b)a=b; }
const int maxn = 210000;

int n,m,Q;
string S,T;
int a[maxn],b[maxn];
int nex[maxn][27];

int f[22][22];

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>S>>T;
		n=S.size(),m=T.size();
		S=' '+S,T=' '+T;
		for(int i=1;i<=n;i++) a[i]=S[i]-'a'+1;
		for(int i=1;i<=m;i++) b[i]=T[i]-'a'+1;
		
		for(int c=1;c<=26;c++) nex[n+1][c]=n+1;
		for(int i=n;i>=1;i--)
		{
			for(int j=1;j<=26;j++) nex[i][j]=nex[i+1][j];
			nex[i][a[i]]=i;
		}
		
		cin>>Q;
		while(Q--)
		{
			int l,r; cin>>l>>r;
			memset(f,-1,sizeof f);
			f[0][0]=l-1;
			for(int i=0;i<m;i++)
			{
				for(int j=0;j<=i;j++) if(f[i][j]!=-1 && f[i][j]<=r)
				{
					upd(f[i+1][j],f[i][j]);
					int p=nex[ f[i][j]+1 ][ b[i+1] ];
					upd(f[i+1][j+1],p);
				}
			}
			
			int ans=0;
			for(int j=0;j<=m;j++) if(f[m][j]<=r && f[m][j]!=-1)
				ans=max(ans,j);
			cout<<r-l+1+m-ans*2<<'\n';
		}
	}
	
	return 0;
}