import java.util.Scanner;        public class Main {        public static void main(String[] args) {            Scanner cin = new Scanner(System.in);            int n = cin.nextInt();            int[] len = new int[n];            for (int k = 0; k < n; k++) {                String s1 = cin.next();                String s2 = cin.next();                int[][] m = new int[s1.length()+1][s2.length()+1];                    for (int i = 0; i < s1.length(); i++) {                    for (int j = 0; j < s2.length(); j++) {                        m[i][j] = 0;                    }                }                                for (int i = 0; i < s1.length(); i++) {                    for (int j = 0; j < s2.length(); j++) {                        if (s1.charAt(i) == s2.charAt(j)) {                            m[i + 1][j + 1] = m[i][j] + 1;                        } else {                            m[i + 1][j + 1] = Math.max(m[i][j + 1], m[i + 1][j]);                        }                    }                }                                len[k] = m[s1.length()][s2.length()];            }            for (int i = 0; i < n; i++) {                System.out.println(len[i]);            }            }    }