// Original C++ solution (slower):
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>

#include <cstdlib>

#include <string>

#include <iostream>

#include <queue>



using namespace std;



const char *X, *Y;

int X_length, Y_length;



int table_lcs[1001][1001];



int lcs(int x_begin, int y_begin) {

	int i, j, to;

	int max = 0;

	int v_lcs;

	bool alreadySeenTable[256];

	if (table_lcs[x_begin][y_begin] != -1) {

		return table_lcs[x_begin][y_begin];

	}

	

	for (i = 0; i < 256; i++) {

		alreadySeenTable[i] = false;

	}

	i = x_begin;

	to = Y_length-1;

	while(i <= X_length-1) {

		j = y_begin;

		if (alreadySeenTable[X[i]] == true) {

			i++;

			continue;

		}

		bool found = false;

		while (j <= to) {

			if (X[i] == Y[j]) {

				v_lcs = lcs(i + 1, j + 1) + 1;

				if (v_lcs > max) {

					max = v_lcs;

				}

				found = true;

				break;

			}

			else {

				j++;

			}

		}

		if (found == false) {

			alreadySeenTable[X[i]] = true;

			i++;

		}

		else {

			alreadySeenTable[X[i]] = true;

			i++;

			to = j - 1;

		}

	}

	return table_lcs[x_begin][y_begin] = max;

}



int lcs2(int x_begin, int y_begin) {

	int i, j, to;

	int max = 0;

	int v_lcs;

	if (table_lcs[x_begin][y_begin] != -1) {

		return table_lcs[x_begin][y_begin];

	}



	i = x_begin;

	to = Y_length - 1;

	while (i <= X_length - 1) {

		j = y_begin;

		bool found = false;

		while (j <= to) {

			if (X[i] == Y[j]) {

				v_lcs = lcs2(i + 1, j + 1) + 1;

				if (v_lcs > max) {

					max = v_lcs;

				}

				found = true;

				break;

			}

			else {

				j++;

			}

		}

		if (found == false) {

			i++;

		}

		else {

			i++;

			to = j - 1;

		}

	}

	return table_lcs[x_begin][y_begin] = max;

}



int main() {



	int N;

	cin >> N;

	string stringX, stringY;



	for (int i = 1; i <= N; i++) {

		for (int i = 0; i < 1001; i++) {

			for (int j = 0; j < 1001; j++) {

				table_lcs[i][j] = -1;

			}

		}

		cin >> stringX >> stringY;

		X = stringX.c_str();

		X_length = stringX.size();

		Y = stringY.c_str();

		Y_length = stringY.size();

		printf("%d\n", lcs2(0, 0));

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <string>

#include <algorithm>

using namespace std;



int lengthOfLcs_r(const char x[], const char y[], int ix, int iy, int xsize, int ysize, int **lengthTable) {

	if (ix == xsize || iy == ysize) {

		return 0;

	}

	if (lengthTable[ix][iy] != -1) {

		return lengthTable[ix][iy];

	}

	if (x[ix] == y[iy]) {

		return lengthTable[ix][iy] = lengthOfLcs_r(x, y, ix + 1, iy + 1, xsize, ysize, lengthTable) + 1;

	}

	return lengthTable[ix][iy] = max(lengthOfLcs_r(x, y, ix, iy + 1, xsize, ysize, lengthTable), lengthOfLcs_r(x, y, ix + 1, iy, xsize, ysize, lengthTable));

}



int lengthOfLcs(string x, string y) {

	int xsize = x.size(), ysize = y.size();



	int **lengthTable = new int*[xsize];

	for (int i = 0; i < xsize; ++i) {

		lengthTable[i] = new int[ysize];

		fill_n(lengthTable[i], ysize, -1);

	}



	int ret = lengthOfLcs_r(x.c_str(), y.c_str(), 0, 0, xsize, ysize, lengthTable);

	

	for (int i = 0; i < xsize; i++) {

		delete[] lengthTable[i];

	}

	delete[] lengthTable;

	

	return ret;

}



int main() {

	int q;

	string x, y;



	cin >> q;

	for (int i = 0; i < q; ++i) {

		cin >> x >> y;

		cout << lengthOfLcs(x, y) << endl;

	}

	return 0;

}


// Fastest known solution for this problem: