Cho hai xâu ~s_1~ và ~s_2~ chỉ chứa các ký tự chữ cái Latin (~a-z, A-Z~).

Hãy tìm độ dài của dãy con chung dài nhất của chúng.

Yêu cầu: Tính và in ra độ dài của dãy con chung dài nhất của hai chuỗi ~s_1~ và ~s_2~.

Input

• Dòng thứ nhất: Chuỗi ký tự ~s_1~ (~1 \leq |s_1| \leq 2000~).
• Dòng thứ hai: Chuỗi ký tự ~s_2~ (~1 \leq |s_2| \leq 2000~).

Output

Một số nguyên duy nhất — độ dài của dãy con chung dài nhất của hai chuỗi.

Example input 1

ABCBDAB
BDCAB

Example output 1

4

Note 1

• Các dãy con chung dài nhất có thể là: BCAB, BDAB. → Độ dài của dãy con chung dài nhất là ~4~.