#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define srep(i, l, r) for (int i = l; i < r; i++)
#define sper(i, r, l) for (int i = r; i > l; i--)
#define maxn 200022
#define maxm 32
#define maxsig 26
using namespace std;

int n, m, q;
int dp[maxm][maxm];
char s[maxn], t[maxm];

int fir[maxm][maxsig];

struct query{
	int x, y, i;
	query(int x, int y, int i) : x(x), y(y), i(i){}
	query(){}
	bool operator < (const query b) const{
		return x == b.x ? y == b.y ? i < b.i : y < b.y : x < b.x;
	}
}que[maxn];

int ans[maxn];

int main(){
	int T, x, y; scanf("%d", &T);
	while (T--) {
		scanf("%s%s", s + 1, t + 1);
		n = strlen(s + 1), m = strlen(t + 1);
		
		rep(k, 1, m) {
			rep(i, 0, 25) {
				fir[k][i] = m + 22;
				rep(j, k, m) {
					if (t[j] - 'a' == i) {
						fir[k][i] = j;
						break;
					}
				}
			}
		}
		
		
		scanf("%d", &q);
		rep(i, 1, q) {
			scanf("%d%d", &x, &y);
			que[i] = query(x, y, i);
		}
		sort(que + 1, que + 1 + q);
		int ptr = q;
		
		rep(p, 1, m + 1) {
			rep(l, 1, m) {
				dp[p][l] = n + 22;
			}
		}
		per(i, n, 1) {
			
			rep(p, 1, m) {
				per(l, m, 1) {
					if (fir[p][s[i] - 'a'] <= m) {
						
						int dd = -1;
						if (l - 1 == 0) dd = i;
						else dd = dp[fir[p][s[i] - 'a'] + 1][l - 1];
						
						dp[p][l] = min(dp[p][l], dd);
					}
				}
			}
				
			while (ptr >= 1 && que[ptr].x == i) {
				per(l, m, 1) {
					if (que[ptr].y >= dp[1][l]) {
						ans[que[ptr].i] = (y - x + 1) + m - 2 * l;
						goto done;
					}
				}
				ans[que[ptr].i] = (y - x + 1) + m;
				done:ptr--;
			}
		}
		
		rep(i, 1, q) printf("%d\n", ans[i]);
	}
	return 0;
}