content: //{ Driver Code Starts
  import java.io.*;
  import java.lang.*;
  import java.util.*;
  
  class GFG {
      public static void main(String[] args) {
  
          Scanner sc = new Scanner(System.in);
          int test = sc.nextInt();
          while (test-- > 0) {
              String s1 = sc.next(); // Take both the strings as input
              String s2 = sc.next();
  
              Solution obj = new Solution();
  
              // Call the lcs function with the lengths of the strings as
              // parameters
              System.out.println(obj.lcs(s1, s2));
              System.out.println("~");
          }
          sc.close();
      }
  }
  
  // } Driver Code Ends
  
  
  class Solution {
      static int lcs(String s1, String s2) {
          // code here
          int n = s1.length();
          int m = s2.length();
          int [][]dp = new int[n+1][m+1];
          
          for(int i=1;i<=n;i++){
              for(int j=1;j<=m;j++){
                  if(s1.charAt(i-1)==s2.charAt(j-1)){
                      dp[i][j] = 1+dp[i-1][j-1];
                  }else{
                      dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1]);
                  }
              }
          }
          return dp[n][m];
      }
  }