// Arup Guha
// 7/23/2014
// Solution to 2014 SI@UCF Contest Problem: Baby Names

import java.util.*;

public class names {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process all cases.
		for (int loop=0; loop<numCases; loop++) {
			char[] mom = stdin.next().toCharArray();
			char[] dad = stdin.next().toCharArray();
			System.out.println(lcs(mom,dad));
		}
	}

	// Returns one LCS of s and t.
	public static String lcs(char[] s, char[] t) {

		// Run standard LCS DP.
		int[][] dp = new int[s.length+1][t.length+1];
		for (int i=1; i<=s.length; i++)
			for (int j=1; j<=t.length; j++)
				if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
				else dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);

		// Here is the build back.
		String ans = "";
		int x = s.length, y = t.length;
		while (x > 0 && y > 0) {

			// Matching letter.
			if (s[x-1] == t[y-1]) {
				ans = s[x-1] + ans;
				x--;
				y--;
			}

			// I look to "go up" first before I go "left".
			else if (dp[x][y] == dp[x-1][y]) x--;
			else y--;
		}

		// The answer.
		return ans;
	}
}