#include <bits/stdc++.h>
using namespace std;
const int maxn = 100025;

int dp[maxn][21][21];
int mx[maxn][21];

void chmax(int &x, int v) {
    if (x < v)
        x = v;
}

void solve() {
    string A, B;
    cin >> A >> B;
    const int N = (int)A.size(), M = (int)B.size();
    A = '$' + A;
    B = '$' + B;
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            for (int k = 0; k <= M; k++) {
                chmax(dp[i][j][k], dp[i-1][j][k]);
                chmax(dp[i][j][k], dp[i][j-1][k]);
                if (A[i] == B[j] && k > 0)
                    chmax(dp[i][j][k], k == 1 ? i : dp[i-1][j-1][k-1]);
            }
        }
        for (int k = 0; k <= M; k++) {
            mx[i][k] = -1;
            for (int j = 1; j <= M; j++) {
                mx[i][k] = max(mx[i][k], dp[i][j][k]);
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int ans = 0;
        for (int k = M; k >= 1; k--) {
            if (mx[r][k] >= l) {
                ans = k;
                break;
            }
        }
        cout << M + (r - l + 1) - ans * 2 << '\n';
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t; cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}