Gizem and Ozan write some texts while doing their ENG101 homework. These texts must be their own individual work. To ensure that, teachers use Turnitin before grading them. The Turnitin is an application that prints similarities in texts to the screen.

If Turnitin prints the longest matching part of the assignments which has the most number of the same words, it will be nice for teachers. Because it is enough to check the most similar part of the papers. Gizem and Ozan wants to code Turnitin as a project. They use their ENG101 texts. Gizem's text is \(\mathbf{X}\), Ozan's text is \(\mathbf{Y}\). Unfortunately, they don't have enough time to test their project.

Your task is to find the similar part that has the most number of the same words in the assignments. In this way, Gizem and Ozan can find out their codes are working.

Note: The homeworks of Gizem and Ozan includes 26 lowercase English characters.

Input

The first line contains the number of test cases \(\mathbf{T}\) .

The first line of the each test has \(\mathbf{X}\), the Gizem's homework.

The second line of the each test has \(\mathbf{Y}\), the Ozan's homework.

• \(1 \leq \mathbf{T} \leq 100\)
• \(1 \leq \mathbf{len(X),len(Y)} \leq 4000\)

where len(str) symbolizes length of the string

Output

Print the number of words in the similarity that has most word.

Example

Input:

3
since smart cities use information technologies we can discuss the privacy problem
not only smart cities use information technologies but also ecocities use it
sehmettin ahmet mehmet
ahmet mehmet sehmettin
i love eating profiterols and drinking coffee at cati 
i love eating pizza and drinking coffee at cati

Output:

5
2
5

Explanation:

• The first answer is 5 because "smart cities use information technologies" has the longest number of words.
• The second answer is 2 because "ahmet mehmet" has the longest number of words.
• The third answer is 5 because "and drinking coffee at cati" has the longest number of words.