Common Subsequence#1774

Common Subsequence

1 second
16 megabytes
Very easy

A subsequence of a given sequence is obtained by deleting some elements (possibly none) from the original sequence. Given a sequence X = \langle x_1, x_2, \ldots, x_m \rangle, another sequence Z = \langle z_1, z_2, \ldots, z_k \rangle is a subsequence of if there is a strictly increasing sequence of indices \langle i_1, i_2, \ldots, i_k \rangle such that for all j = 1, 2, \ldots, k, x_{i_j} = z_j. For example, Z = \langle a, b, f, c \rangle is a subsequence of X = \langle a, b, c, f, b, c \rangle with indices \langle 1, 2, 4, 6 \rangle.

Given two sequences and , find the length of the longest common subsequence of and .

Input

The input consists of several data sets. Each data set contains two strings representing the sequences, separated by any number of spaces. The input data are correct.

Output

For each data set, output the length of the longest common subsequence, one per line.

Examples

Example 1

Loading
Loading