Độ dài xâu con chung

Xâu \(R\) được gọi là xâu con của xâu \(S\) nếu có thể thu được \(R\) từ \(S\) bằng cách xoá đi một số (có thể không có) ký tự của \(S\) và giữ nguyên thứ tự các ký tự còn lại.

Cho hai xâu \(A\) và \(B\). Hãy tính độ dài của xâu con chung dài nhất, tức là xâu vừa là xâu con của \(A\) vừa là xâu con của \(B\) và có độ dài lớn nhất.

Input

• Dòng thứ nhất chứa xâu \(A\).
• Dòng thứ hai chứa xâu \(B\).

Output

In ra một số nguyên là độ dài lớn nhất của một xâu con chung của \(A\) và \(B\).

Constraints

• Mỗi xâu có độ dài từ \(1\) đến \(2000\).
• Các xâu chỉ gồm các ký tự in được có mã ASCII từ \(33\) đến \(126\) (không chứa dấu cách).

Sample Input 1

phuongtrinh
trinhphuong

Sample Output 1

6

Sample Input 2

x9k!a7
9!k7xa

Sample Output 2

3

Explanation

Ở ví dụ 1, xâu phuong là một xâu con chung có độ dài \(6\). Ở ví dụ 2, xâu 9!7 là xâu con chung có độ dài \(3\).