import java.util.*;

class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			String a = sc.next();
			String b = sc.next();
			int[][]lcs=new int[a.length()+1][b.length()+1];
			for(int z=1;z<=a.length();z++) {
				for(int y=1;y<=b.length();y++) {
					if(a.charAt(z-1)==b.charAt(y-1)) {
						lcs[z][y]=lcs[z-1][y-1]+1;
					}
					else {
						lcs[z][y]=Math.max(lcs[z-1][y], lcs[z][y-1]);
					}
				}
			}
			System.out.print("#" + t + " ");
			System.out.println(lcs[a.length()][b.length()]);
		}
		sc.close();
	}
}