A common subsequence between two strings A and B is defined as 2 sets { i0 , i1 , i2 , i3 , ... , ik } { j0 , j1 , j2 , j3 , ... , jk } such that 0 <= i0 < i1 < i2 < i3 < ... < A.length() and 0 <= j0 < j1 < j2 < j3 < ... < B.length() and A[ i0 ] = B[ j0 ], A[ i1 ] = B[ j1 ] , ... , A[ ik ] = B[ jk ]. Given two strings A and B print the length of the longest common subsequence between them.

i.e. "a", "d","cd" are common subsequence between the two strings "abcd" and "adcd" while "acd" is the longest common subsequence between them.

Input

First line contains a string A (1 <= A.lenth() <= 7).

Second line contains a string B (1 <= B.length() <= 7).

Each string is composed of lower case letters only ('a' -'z').

Output

Prints one line containing the length of the longest common subsequence.

Example

Input:

abcd

adcd

Output:
3