Longest Common Subsequence

Given two strings (S) and (T), your task is to compute the length of their longest common subsequence (LCS). A subsequence of a string is a sequence that can be derived from the string by deleting some (or no) characters without changing the order of the remaining characters. For example, the LCS of "abcde" and "ace" is "ace", which has a length of 3.

The problem can be solved using dynamic programming. The recurrence relation is given by: [ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{if } S[i-1] = T[j-1] \ \max(dp[i-1][j],; dp[i][j-1]), & \text{otherwise} \end{cases} ]

You are required to handle multiple test cases. For each test case, output the length of the LCS on a new line.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (Q) representing the number of test cases. Each of the following (Q) lines contains two space-separated strings (S) and (T).

outputFormat

For each test case, print a single integer representing the length of the longest common subsequence between the two strings. The results for multiple test cases should be printed on separate lines on standard output (stdout).## sample

3
abcde ace
xyz yz
abcdef ghijkl

3
2
0