Bài 2. Mức độ giống nhau của hai bài làm

Mô tả

Hai học sinh nộp hai chuỗi đáp án trắc nghiệm, mỗi chuỗi chỉ gồm các ký tự A, B, C, D.
Hãy xác định số câu tối đa mà hai bài có thể được xem là giống nhau theo thứ tự, tức là độ dài dãy con chung dài nhất của hai chuỗi.

Input

• Dòng 1 chứa chuỗi đáp án của học sinh thứ nhất.
• Dòng 2 chứa chuỗi đáp án của học sinh thứ hai.

Output

• In ra độ dài LCS của hai chuỗi.

Ràng buộc

• 1 <= độ dài mỗi chuỗi <= 2000

Subtask

• Subtask 1 (25%): độ dài mỗi chuỗi không quá 200
• Subtask 2 (75%): Không có ràng buộc gì thêm.

Ví dụ

Input

ABCDAB
BACDBA

Output

4

Giải thích ví dụ

Một LCS có thể là ACDA.