//{ Driver Code Starts //Initial Template for Java import java.io.*; import java.util.*; class GFG { public static void main(String args[])throws IOException { BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(read.readLine()); while(t-- > 0) { String input[] = read.readLine().trim().split(" "); int n = Integer.parseInt(input[0]); int m = Integer.parseInt(input[1]); String S1 = read.readLine().trim(); String S2 = read.readLine().trim(); Solution ob = new Solution(); System.out.println(ob.longestCommonSubstr(S1, S2, n, m)); } } } // } Driver Code Ends //User function Template for Java class Solution{ int longestCommonSubstr(String s1, String s2, int m, int n){ /* Q34 of dp playlist , compare all prefixes of both s1 and s2 and find longest common suffix , that will become your longest common substring */ int dp[][] = new int[m+1][n+1]; int ans = 0; //first coloumn and first row will be 0 , which is by default also 0 for(int i = 1 ; i < m+1 ; i++){ for(int j = 1 ; j < n+1; j++){ //if last chars are equal , ans = ansof(prefix) + 1 , ans of prefix //can be found diagonally behind if(s1.charAt(i-1) == s2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1] + 1; ans = Math.max(ans , dp[i][j]); } } } // for(int i = 0 ; i < m ; i++){ // for(int j = 0 ; j<n ; j++){ // System.out.print(dp[i][j] + " "); // } // System.out.println(); // } return ans; } }