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

Xâu ký tự \(C\) được gọi là xâu con chung của hai xâu \(A\) và \(B\) nếu \(C\) là xâu con của \(A\) và \(C\) là xâu con của \(B\). Trong bài tập này nhiệm vụ của bạn cần tìm xâu con chung dài nhất của hai xâu \(A\) và \(B\)

Dữ liệu vào

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

Dữ liệu ra

• In ra một số nguyên duy nhất là độ dài xâu con chung dài nhất của hai xâu đã cho.

Input 1

abcd
aabd

Output 1

3

Input 2

abc1def2ghi3
abcdefghi123

Output 2

10