#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int M = 22;
const int S = 26;
const int inf = 0x3f3f3f3f;

int n, m;
char a[N], b[M];

int nxt[N][S] = {{0}}; 

int f[M][M] = {{0}};

void cmn(int &x, int y) {
	x = min(x, y);
}

void slv() {
	scanf("%s", a + 1);
	scanf("%s", b + 1);
	n = strlen(a + 1), m = strlen(b + 1);
	for (int j = 0; j < S; j++)
		nxt[n][j] = n + 1;
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < S; j++)
			nxt[i][j] = nxt[i + 1][j];
		nxt[i][a[i + 1] - 'a'] = i + 1;
	}
	int q;
	scanf("%d", &q);
	while (q--) {
		int l, r;
		scanf("%d%d", &l, &r);
		for (int i = 0; i <= m; i++)
			for (int j = 0; j <= m; j++)
				f[i][j] = inf;
		f[0][0] = l - 1;
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= m; j++) {
				if (i > 0)
					cmn(f[i][j], f[i - 1][j]);
				if (i > 0 && j > 0 && f[i - 1][j - 1] != inf && nxt[f[i - 1][j - 1]][b[i] - 'a'] <= r)
					cmn(f[i][j], nxt[f[i - 1][j - 1]][b[i] - 'a']);
			}
		}
		int ans = 0;
		for (int i = m; i >= 1; i--)
			if (f[m][i] <= r) {
				ans = i;
				break;
			}
		printf("%d\n", r - l + 1 + m - 2 * ans);
	}
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--)
		slv();	
	return 0;
}