Longest Common Substring

You are given two strings. Your task is to determine the length of the longest common substring shared between them. A substring is a contiguous sequence of characters. For two strings \( a \) and \( b \), you need to find the maximum length \( L \) such that there exists a substring \( s \) with \( |s| = L \) and \( s \) appears in both \( a \) and \( b \).

Note: The problem should be solved using a dynamic programming approach. The recurrence relation for the algorithm can be described as:

[ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1] + 1, & \text{if } a_i = b_j \ 0, & \text{otherwise} \end{cases} ]

where \( a_i \) and \( b_j \) represent the \( i^{th} \) and \( j^{th} \) characters of strings \( a \) and \( b \) respectively. The result is the maximum value in the dp table.

inputFormat

The first line of input contains a single integer \( T \) representing the number of test cases. Each test case consists of two lines:

• The first line contains a non-empty string \( a \).
• The second line contains a non-empty string \( b \).

You should process each test case independently.

outputFormat

For each test case, output a single line containing an integer that represents the length of the longest common substring between the two given strings.

## sample

2
abcde
xycdz
aabbcc
ccbbdd

2
2

</p>