#1965 Longest Common Substring

31  1 s   128 MB  

Description

Find two string's longest common substring's length

Input

First line will be Testcase T ( 1 <= T <= 30 )

For each testcase, two strings S1,S2 ( string length < 1,000 ) will be given.

Output

Print the longest common substring's length

Sample Input

Sample Output

1
PARKCHUYOUNG
PARKJISUNG
4

HINT

PARKCHUYOUNG
PARKJISUNG

4