Trong bài này, ta gọi xâu x là xâu con của xâu y nếu như có thể xóa một số kí tự của y (có thể không xóa kí tự nào) để nó trở thành xâu x. VD xâu "ABC" là xâu con của "AABDEC" nhưng không phải là xâu con của "BACCA".

Cho 2 xâu a và b. Tìm xâu con chung dài nhất của a và b. Ghi ra độ dài của xâu con chung đó.

Input

Dòng 1: Xâu a;

Dòng 2: Xâu b;

Mỗi xâu không quá 5000 kí tự;

Output

Ghi ra độ dài xâu con chung dài nhất.

Ví dụ:

Input

abcdgh
bacesgo

Output

3

Giải thích:

Các xâu con chung dài nhất của 2 xâu đã cho trong ví dụ là "acg" hoặc "bcg" (đều có độ dài 3).