Longest Common Subsequence

Given two strings s1 and s2, determine the length of their longest common subsequence (LCS).

The longest common subsequence of two sequences is defined as the longest sequence that appears in both sequences in the same order (not necessarily consecutively). More formally, if we denote the LCS length by \(LCS(s1, s2)\), then an optimal solution satisfies:

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{if } s1[i-1] = s2[j-1]\\ \max(dp[i-1][j], dp[i][j-1]), & \text{otherwise} \end{cases}$$

Your task is to implement a solution that can process multiple test cases efficiently. Each test case consists of two strings, and your program should output the length of the LCS for each pair.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer T, representing the number of test cases.
• For each test case, there are two consecutive lines:
  • The first line contains the string s1.
  • The second line contains the string s2.

outputFormat

For each test case, print a single line to standard output (stdout) containing the length of the longest common subsequence of the two given strings.

3
abcde
ace
abc
abc
abc
def

3
3
0