Cho hai xâu ký tự A và B gồm các ký tự chữ thường hoặc chữ hoa.

Hãy tìm độ dài của chuỗi con chung dài nhất giữa A và B.

(Một chuỗi con không nhất thiết phải liên tiếp, nhưng phải giữ nguyên thứ tự các ký tự.)

Dữ liệu vào (Input)

Dòng 1: xâu ký tự A (độ dài ≤ 1000)

Dòng 2: xâu ký tự B (độ dài ≤ 1000)

Dữ liệu ra (Output)

In ra độ dài của chuỗi con chung dài nhất (LCS).

Ví dụ:

Input

abcde
ace

Output

3

Giải thích: LCS là "ace" → độ dài = 3.