class Solution:
    #Function to find the length of longest common subsequence in two strings.
    def lcs(self,m,n,a,b):
        # m,n = len(a), len(b)
        dp = [[-1 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                    continue
                if a[i-1] == b[j-1]:
                    dp[i][j] = 1+ dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j] , dp[i][j-1])
        # for i in dp:
        #     print(*i)
        return dp[m][n]

#{ 
#  Driver Code Starts
#Initial Template for Python 3
import atexit
import io
import sys

# Contributed by : Nagendra Jha

if __name__ == '__main__':
    test_cases = int(input())
    for cases in range(test_cases):
        x,y = map(int,input().strip().split())
        s1 = str(input())
        s2 = str(input())
        ob=Solution()
        print(ob.lcs(x,y,s1,s2))
# } Driver Code Ends
fb5e4c5014ddf6f497bf412f09bbffa94a04404d
class Solution:
    <mask token>


<mask token>

class Solution:

    def lcs(self, m, n, a, b):
        dp = [[(-1) for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                    continue
                if a[i - 1] == b[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]


<mask token>

class Solution:

    def lcs(self, m, n, a, b):
        dp = [[(-1) for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                    continue
                if a[i - 1] == b[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]


<mask token>
if __name__ == '__main__':
    test_cases = int(input())
    for cases in range(test_cases):
        x, y = map(int, input().strip().split())
        s1 = str(input())
        s2 = str(input())
        ob = Solution()
        print(ob.lcs(x, y, s1, s2))

class Solution:

    def lcs(self, m, n, a, b):
        dp = [[(-1) for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                    continue
                if a[i - 1] == b[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]


import atexit
import io
import sys
if __name__ == '__main__':
    test_cases = int(input())
    for cases in range(test_cases):
        x, y = map(int, input().strip().split())
        s1 = str(input())
        s2 = str(input())
        ob = Solution()
        print(ob.lcs(x, y, s1, s2))

class Solution:
    #Function to find the length of longest common subsequence in two strings.
    def lcs(self,m,n,a,b):
        # m,n = len(a), len(b)
        dp = [[-1 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                    continue
                if a[i-1] == b[j-1]:
                    dp[i][j] = 1+ dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j] , dp[i][j-1])
        # for i in dp:
        #     print(*i)
        return dp[m][n]

#{ 
#  Driver Code Starts
#Initial Template for Python 3
import atexit
import io
import sys

# Contributed by : Nagendra Jha

if __name__ == '__main__':
    test_cases = int(input())
    for cases in range(test_cases):
        x,y = map(int,input().strip().split())
        s1 = str(input())
        s2 = str(input())
        ob=Solution()
        print(ob.lcs(x,y,s1,s2))
# } Driver Code Ends