Quỳnh mới khai trương một tiệm hoa, cô ấy muốn đặt tên tiệm là \(S_Q\) (một xâu kí tự). Khi Quỳnh hỏi ý kiến của tôi, tôi lại cho rằng tên \(S_T\) mới là đẹp. Hai bên bất đồng quan điểm, để tránh tranh cãi nhiều hơn nữa (có thể dẫn tới việc tôi bị đuổi khỏi nhà), đại ca L giấu tên đã hiến kế như sau: “Chi bằng ta chọn ra một xâu \(S_L\) ngắn nhất, sao cho cả \(S_Q\) và \(S_T\) đều là xâu con* của \(S_L\)”. Cả hội nhất trí, nhưng việc tính toán thì để ai? Tôi thà rửa bát còn hơn phải đụng vào đống giải thuật đã được 'đóng gói' cẩn thận trong kí ức (APAC) …

(*) xâu con (subsequence) là xâu thu được bằng cách xóa đi 0 hoặc nhiều ký tự từ xâu gốc mà vẫn giữ nguyên thứ tự của các ký tự còn lại.

Yêu cầu: Cho hai xâu \(S_Q, S_T\). Hãy tìm xâu \(S_L\) ngắn nhất sao cho \(S_Q, S_T\) là xâu con của nó.

Input

• Dòng đầu tiên chứa xâu \(S_Q\). Dòng thứ hai chứa xâu \(S_T\). Kí hiệu \(|S|\) là độ dài xâu.
• Dữ liệu đảm bảo \(S_Q, S_T\) chỉ chứa kí tự latin in thường và \(1 \leq |S_Q|, |S_T| \leq 2500\).

Output

• Dòng duy nhất chứa độ dài của xâu \(S_L\) tìm được.

Example

qqhana
quynhanh

10

Scoring

• Subtask 1 (\(30\%\) số điểm): \(|S_Q|, |S_T| \leq 5\).
• Subtask 2 (\(30\%\) số điểm): \(|S_Q|, |S_T| \leq 27\).
• Subtask 3 (\(40\%\) số điểm): không có ràng buộc gì thêm.