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\).

Example

abab
baba

3