#include <bits/stdc++.h>


using namespace std;

template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef ONPC
  #define deb(...) cerr << '[' << __FILE__ << ':' << __LINE__ << "] (" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
  #pragma GCC optimize("O3,unroll-loops")
  #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  #define deb(...)
#endif

// c++ short types
#define vt vector
//typedef long long ll;
typedef long double ld;

void whattime() { cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; }
// const int mod = 1e9 + 7;
const int mod = 998244353;
const int inf = 1e9;
const int64_t infll = 1e13;
bool debug = false;
const ld eps = 1e-9;
const ld pi = acos(-1);
mt19937_64 rng((int) chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 10, maxm = 1e3 + 10;
const int K = 26;
int suff[K][maxn];
int dp[maxm][maxm];
char a[maxn], b[maxm];

char skip() {
  char ret;
  do {
    ret = getchar();
  } while(ret < 'a' || ret > 'z');
  return ret;
}

void solve() {
  a[0] = skip() - 'a';
  int n = 1;
  while(true) {
    a[n] = getchar();
    if(a[n] < 'a' || a[n] > 'z') {
      break;
    }
    a[n] -= 'a';
    ++n;
  }
  b[0] = skip() - 'a';
  int m = 1;
  while(true) {
    b[m] = getchar();
    if(b[m] < 'a' || b[m] > 'z') {
      break;
    }
    b[m] -= 'a';
    ++m;
  }
  for(int j = 0; j < K; ++j) {
    suff[j][n] = n;
    for(int i = n-1; i >= 0; --i) {
      suff[j][i] = suff[j][i + 1];
      if(a[i] == j) {
        suff[j][i] = i;
      }
    }
  }
  for(int i = 0; i <= n; ++i) {
    for(int j = 0; j <= n; ++j) {
      dp[i][j] = n + 1;
    }
  }
  dp[0][0] = -1;
  int res = 0;
  for(int x = 1; x <= m; ++x) {
    dp[x][0] = -1;
    for(int y = 1; y <= x; ++y) { 
      dp[x][y] = dp[x-1][y];
      {
        int pos = dp[x-1][y-1];
        if(pos < n and suff[b[x-1]][pos+1] != n) {
          dp[x][y] = min(dp[x][y], suff[b[x-1]][pos+1]);
        }
      }
      if(dp[x][y] < n) {
        res = max(res, y);
      }
    }
  }
  cout << res << '\n';
}

int main()
{
	int tt = 1;;
	if(debug) {
		tt = 1e3;
	} else {
		cin >> tt;
	}

	for(int t = 0; t < tt; ++t) {
		solve();
	}
	
#ifdef ONPC
	whattime();
#endif
	
	return 0;
}