Longest Common Substring

You are given several pairs of strings. For each pair, you are to compute the length of the longest substring that appears in both strings. A substring is a contiguous sequence of characters. The problem requires you to implement an algorithm that finds the longest common substring using dynamic programming techniques.

For example, given the strings abcdxyz and xyzabcd, the longest common substring is abcd with a length of 4. In contrast, if the strings share no common substring, the output should be 0.

The mathematical formulation for the recurrence relation is given by: \[ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 &\text{if } s_1[i] = s_2[j] \\ 0 &\text{otherwise} \end{cases} \] where \( dp[i][j] \) represents the length of the longest common substring ending at position \( i \) in \( s_1 \) and position \( j \) in \( s_2 \).

inputFormat

The first line contains a single integer T (T ≥ 1) indicating the number of test cases. Each test case consists of two lines. The first line contains the first string s1 and the second line contains the second string s2.

Strings may contain any printable characters, and their lengths will be within reasonable limits for the dynamic programming approach.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest common substring between the two given strings.

3
abcdxyz
xyzabcd
abcde
fghij
abcdef
defghi

4
0
3