Given two strings, 'S' and 'T' with lengths 'M' and 'N', find the length of the 'Longest Common Subsequence'.

For a string 'str'(per se) of length K, the subsequences are the strings containing characters in the same relative order as they are present in 'str,' but not necessarily contiguous. Subsequences contain all the strings of length varying from 0 to K.

Example :

Subsequences of string "abc" are:  ""(empty string), a, b, c, ab, bc, ac, abc.

Input format :

The first line of input contains the string 'S' of length 'M'.

The second line of the input contains the string 'T' of length 'N'.

Output format :

Return the length of the Longest Common Subsequence.

Constraints :

0 <= M <= 10 ^ 3
0 <= N <= 10 ^ 3

Time Limit: 1 sec