#include <bits/stdc++.h>
using namespace std ;
char a[100010] , b[25] ;
int dy[25][100010] ;
int dc[25] , la , lb ;
int q ;
int dp[25][25] ;//dp[a][b] = c: b匹配到a，匹配了b个，a最小匹配到c
inline int ef( int t1 , int t2 , int wz )//在a的t1、t2间找b[wz]
{
	if( dc[wz] == 0 ) return -1 ;
	int l = 0 , r = dc[wz] - 1 , mid , ans = dc[wz] - 1 ;
	while( l <= r )
	{
		mid = ( l + r ) / 2 ;
		if( dy[wz][mid] >= t1 )
		{
			ans = mid ;
			r = mid - 1 ;
		}
		else
		{
			l = mid + 1 ;
		}
	}
//	cout<< dy[wz][ans] << endl ;
	if( dy[wz][ans] > t2 ) return -1 ;
	return ans ;
}
int main ()
{
	int t1 , t2 ;
	int t ;
	scanf( "%d" , &t ) ;
	while( t -- )
	{
		memset( dc , 0 , sizeof(dc) ) ;
		scanf( "%s" , &a ) ;
		scanf( "%s" , &b ) ;
		la = strlen(a) ;
		lb = strlen(b) ;
		if( t == 9 )
		{
			for( int i = 0 ; i < lb ; i ++ )
			{
				cout<< b[i] ;
			}
			cout<< endl ;
		}
		for( int i = 0 ; i < la ; i ++ )
		{
			for( int j = 0 ; j < lb ; j ++ )
			{
				if( a[i] == b[j] )
				{
					dy[j][dc[j]] = i ;
					dc[j] ++ ;
				}
			}
		}
		scanf( "%d" , &q ) ;
		for( int i = 0 ; i < q ; i ++ )
		{
			memset( dp , -1 , sizeof(dp) ) ;
			scanf( "%d%d" , &t1 , &t2 ) ;
			if( t == 9 && i == 88 )
			{
				cout<< t1 << ' ' << t2 << endl ;
			}
			t1 -- ;
			t2 -- ;
			dp[0][0] = t1 ;
			int tmp = ef( t1 , t2 , 0 ) ;
			if( tmp != -1 ) dp[0][1] = tmp + 1 ;
			for( int i = 1 ; i < lb ; i ++ )
			{
				for( int j = 0 ; j <= i + 1 ; j ++ )
				{
					dp[i][j] = dp[i - 1][j] ;
					if( j != 0 )
					{
						if( dp[i - 1][j - 1] == -1 ) continue ;
						int tmp = ef( dp[i - 1][j - 1] , t2 , i ) ;
						if( tmp != -1 )
						{
							tmp = dy[i][tmp] ;
							if( dp[i][j] == -1 || dp[i][j] > tmp )
							{
								dp[i][j] = tmp + 1 ;
							}
						}
					}
				}
			}
			int ans = 0 ;
			for( int i = lb ; i >= 0 ; i -- )
			{
				if( dp[lb - 1][i] != -1 )
				{
					ans = i ;
					break ;
				}
			}
			printf( "%d\n" , t2 - t1 + 1 - ans + lb - ans ) ;
		}
	}
	return 0 ;
}