GREATEST COMMON SUBSEQUENCE

Program

GCS.PAS, GCS.C, GCS.CPP)

Your task is to write a program that computes the LENGTH of the longest common substring of two given strings. The substring does not have to be connected.

Examples:						longest
							common
string 1		string 2	substring	length
-------------------------------------------------------
abcabcabc		aabbcc	abbcc		5
					aabcc		5
					aabbc		5

belaljubljana	belakrajina	belajna	7

xxxyyyzzz		aaabbbccc			0

Note that in the first example there are several different longest common substrings, but they all have the same length. You may assume all strings consist of lower-case letters only.Your program should work for fairly long strings (several hundred characters long).

INPUT DATA:

The file GCS.IN contains in the first line an integer N.The rest of the file contains 2*N lines which represent N input pairs of strings.

OUTPUT DATA:

N lines of output, the k-th line contains an integer which is the length of the longest common substring of the (2*k)-th and (2*k+1)-th input string.

SAMPLE INPUT AND OUPUT:

INPUT:
3 ikarus dedalus onetwothreefour fivesixseveneight odnekdajlepesoljubljankeslovele allepseodurskebiloninobene

OUTPUT:
3 3 13