Sequence 1:  

Sequence 2: 

Given two sequences of characters, print the length of the longest common subsequence of both sequences. For example, the longest common subsequence of the following two sequences:

abcdgh aedfhr 

is adh of length 3.

Input consists of pairs of lines. The first line of a pair contains the first string and the second line contains the second string. Each string is on a separate line and consists of at most 1,000 characters

For each subsequent pair of input lines, output a line containing one integer number which satisfies the criteria stated above.