#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); i++)
#define revrep(i, a, n) for (auto i = n; i >= (a); i--)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } else return 0; }
using namespace std;

template<class A, class B> string to_string(pair<A, B> p);
template<class A> string to_string(A v) {
	bool first = 1;
	string res = "{";
	for (auto x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B> string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(H h, T... t) {
	cerr << " " << to_string(h);
	debug_out(t...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

const int inf = 0x3f3f3f3f;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int cas; cin >> cas; while (cas--) {
		string s, t; cin >> s >> t;
		int n = sz(s), m = sz(t);
		int q; cin >> q;
		vvi nxt(n + 1, vi(26, inf));
		revrep(i, 0, n - 1) {
			int c = s[i] - 'a';
			nxt[i] = nxt[i + 1];
			nxt[i][c] = i;
		}
		while (q--) {
			int l, r; cin >> l >> r;
			l--, r--;
			vi dp(m + 1, inf);
			dp[0] = l - 1;
			rep(ind, 0, m - 1) {
				int c = t[ind] - 'a';
				vi ndp = dp;
				rep(i, 0, m - 1) {
					if (dp[i] + 1 <= r && nxt[dp[i] + 1][c] <= r) chmin(ndp[i + 1], nxt[dp[i] + 1][c]);
				}
				swap(dp, ndp);
			}
			int lcs = 0;
			rep(i, 0, m) if (dp[i] <= r) chmax(lcs, i);
			printf("%d\n", r - l + 1 + m - lcs * 2);
		}		
	}
	return 0;
}