Longest Common Substring

You are given two strings A and B. Your task is to find the length of the longest substring that appears in both A and B. A substring is a contiguous sequence of characters within a string. For example, for strings A = "abcdxyz" and B = "xyzabcd", the longest common substring is abcd with length 4.

A common approach to solve this problem is using dynamic programming. In particular, we can define a DP table such that:

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } A[i-1] = B[j-1] \\ 0 & \text{otherwise} \end{cases} $$

The answer is the maximum value in the DP table.

inputFormat

The first line contains an integer T representing the number of test cases. For each test case, there are two consecutive lines, where the first line is the string A and the second line is the string B.

Example:

2
abcde
fghij
abcde
bcfgh

outputFormat

For each test case, output a single line containing the length of the longest common substring of A and B.

Example:

0
2

## sample

5
abcde
fghij
abcde
bcfgh
abcdxyz
xyzabcd
aaaaa
aaaaa
abcdef
cdefgh

0
2
4
5
4

</p>