Longest Common Substring Length

Given two strings S and T, your task is to determine the length of the longest subsequence of S that appears as a contiguous substring in T.

Note that a substring of T is a contiguous block of characters, while a subsequence of S is a sequence that can be derived from S by deleting some characters without changing the order. In this problem, you are effectively being asked to find the longest common substring between S and T.

For each query, output the length of the longest common substring. If there is no common substring, output 0.

Examples:

• S = "abc" and T = "abcd" result in 3 because "abc" is a substring of T.
• S = "xyz" and T = "xyzxyz" result in 3.
• S = "abc" and T = "xyxaybyc" result in 1, since only individual characters match contiguously.

inputFormat

The input is given from stdin and it has the following format:

1. The first line contains an integer Q, the number of queries.
2. Then for each query, there are two lines:
   • The first line is the string S.
   • The second line is the string T.

outputFormat

For each query, output a single line containing the length of the longest common substring between S and T. The output should be written to stdout.

## sample

3
abc
abcd
xyz
xyzxyz
abc
xyxaybyc

3
3
1

</p>