Description

Given two strings, find the length of the longest common substring.

Input

The first line of input contains a positive integer t , which indicates the number of test cases. For each case, there are two strings in a line (length of the string <= 1000).

Case1: O(n³) T <= 10 , length of string <= 100
Case2: O(n²) T <= 100 , length of string <= 1000
Case3: O(n²) T <= 100 , length of string <= 1000
Case4: O(n²) T <= 500 , length of string <= 1000

Output

Output the length of the longest common substring.

Sample Input  Download

Sample Output  Download

Tags

Discuss