Cho hai xâu \(S\) và \(T\) chỉ gồm các chữ cái in thường. Tìm độ dài xâu con chung dài nhất (Subsequence) của hai xâu \(S\) và \(T\).

Input

• Dòng đầu tiên chứa xâu \(S\).
• Dòng thứ hai chứa xâu \(T\).

Output

• In ra một số nguyên dương duy nhất là độ dài xâu con chung dài nhất của \(S\) và \(T\).

Constraints

• \(|S|\geq |T|\).
• \(|S|.|T|\leq 5.10^9\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(|S|,|T|\leq 5.10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(|T|\leq 5.10^3,|S|\leq 10^6\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm

Example

hhoangcpascal
xzitthamer 

2