An và Bình cùng làm bài tập nhóm môn Tiếng Việt mà cô giáo vừa giao về nhà. Bạn An viết một xâu ký tự \(S\), bạn Bình viết một xâu ký tự \(T\) (cả hai xâu đều gồm các chữ cái Latin in thường). Hai bạn phải tìm ra một dãy ký tự xuất hiện theo đúng thứ tự ở cả hai xâu, các ký tự không nhất thiết phải đứng liền nhau khi lấy từ xâu gốc. Dãy càng dài thì hai bạn càng được khen.

Hãy giúp An và Bình tìm độ dài lớn nhất của dãy ký tự chung như vậy.

Định dạng đầu vào

• Dòng đầu tiên chứa xâu \(S\) (độ dài \(|S| \le 5000\)).
• Dòng thứ hai chứa xâu \(T\) (độ dài \(|T| \le 5000\)).
• Các xâu chỉ gồm chữ cái Latin in thường.

Định dạng đầu ra

• In ra độ dài dãy ký tự chung dài nhất.

Ví dụ

Input:

abcde
ace

Output:

3

Ràng buộc

• \(30\%\) số điểm ứng với \(|S|, |T| \le 100\).
• \(30\%\) số điểm ứng với \(|S|, |T| \le 1000\).
• \(40\%\) số điểm còn lại không có ràng buộc gì thêm.