Common Subsequence

A sequence Z is a subsequence of a sequence X if it can be obtained by deleting zero or more elements without changing the order of the remaining elements. Given two strings, find the length of their longest common subsequence.

Input

The input contains multiple data sets until end of file. Each data set consists of two whitespace-separated strings.

Output

For each pair, print the length of a longest common subsequence.

Example

Input:

abcfbc abfcab
programming contest
abcd mnp

Output:

4
2
0