#include<bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
#define pii pair<int,int>
#define pb push_back
#define umap unordered_map
#define mset multiset
#define pq priority_queue
#define ull unsigned long long
#define i128 __int128
const int maxn=1e5+10;
int n,m,q,dp[25][25],nxt[maxn][26];
//dp[i][j]:当前匹配到 t 的前 i 个，lcs 为 j 的最小下标
string s,t;
void read(string &str,int &len){
    cin>>str,len=str.size(),str=" "+str;
}
void solve(){
    read(s,n),read(t,m);
    for(int i=0;i<26;i++) nxt[n+1][i]=n+1;
    for(int i=n;i;i--){
        for(int j=0;j<26;j++) nxt[i][j]=(s[i]==('a'+j)?i:nxt[i+1][j]);
    }
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        for(int i=0;i<=m;i++){
            for(int j=0;j<=m;j++) dp[i][j]=r+1;
        }dp[0][0]=l-1;
        for(int i=1;i<=m;i++){
            dp[i][0]=dp[i-1][0];
            for(int j=1;j<=m;j++){
                dp[i][j]=dp[i-1][j];
                if(dp[i-1][j-1]<=r) dp[i][j]=min(dp[i][j],nxt[dp[i-1][j-1]+1][t[i]-'a']);
            }
        }
        // for(int i=1;i<=m;i++,cout<<endl){
        //     for(int j=1;j<=m;j++){
        //         cout<<dp[i][j]<<" ";
        //     }
        // }
        int maxx=0;
        for(int i=1;i<=m;i++){
            if(dp[m][i]<=r) maxx=max(maxx,i);
        }
        cout<<r-l+1+m-2*maxx<<endl;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}
/*
Samples
input:

output:

THINGS TODO:
检查freopen，尤其是后缀名
检查空间
检查调试语句是否全部注释
*/