#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 == 322 )
//			{
//				cout<< t1 << ' ' << t2 << endl ;
//				return 0 ;
//			}
			t1 -- ;
			t2 -- ;
			dp[0][0] = t1 ;
			int tmp = ef( t1 , t2 , 0 ) ;
//			cout<< "A" << tmp << ' ' << endl ;
			if( tmp != -1 ) dp[0][1] = dy[0][tmp] + 1 ;
//			cout<< dp[0][0] << ' ' << dp[0][1] << endl ;
			for( int i1 = 1 ; i1 < lb ; i1 ++ )
			{
				for( int j = 0 ; j <= i1 + 1 ; j ++ )
				{
					dp[i1][j] = dp[i1 - 1][j] ;
					if( j != 0 )
					{
						if( dp[i1 - 1][j - 1] != -1 )
						{
							int tmp = ef( dp[i1 - 1][j - 1] , t2 , i1 ) ;
//							cout<< tmp << endl ;
							if( tmp != -1 )
							{
								tmp = dy[i1][tmp] ;
								if( dp[i1][j] == -1 || dp[i1][j] > tmp )
								{
									dp[i1][j] = tmp + 1 ;
								}
							}
						}
					}
				}
				if( i == 322 ) cout<< dp[i1][i1 - 6] << " " << dp[i1][i1 - 7] << "  ";
//				cout<< endl ;
			}
			if( i == 322 ) return 0 ;
			int ans = 0 ;
			for( int i1 = lb ; i1 >= 0 ; i1 -- )
			{
				if( dp[lb - 1][i1] != -1 )
				{
					ans = i1 ;
					break ;
				}
			}
			printf( "%d\n" , t2 - t1 + 1 - ans + lb - ans ) ;
		}
	}
	return 0 ;
}