Cho ~S~ là một xâu kí tự ta gọi xâu lặp bậc ~K~ của ~S~, kí hiệu ~S^k~ là xâu tạo thành bằng cách nối liên tiếp xâu ~S~ đúng ~K~ lần.

Ví dụ xâu ~sossossos~ là xâu lặp bậc 3 của xâu ~sos~. Định nghĩa xâu ~A~ là xâu con của ~B~ nếu ta có thể xóa vài kí tự trong ~B~ để được xâu ~A~. ví dụ xâu ~gotwin~ là xâu con của xâu ~gonewtihthewind~.

Yêu cầu: cho hai xâu ~S~ và ~T~. Hãy tìm xâu lặp lớn nhất của ~S~ là xâu con của ~T~ và cho biết bậc của nó.

Dữ liệu vào

• Dòng 1 ghi xâu ~S~ bao gồm các kí tự thường trong bảng chữ cái.
• Dòng 2 ghi xâu ~T~ bao gồm các kí tự thường trong bảng chữ cái.

Kết quả

Số ~K~ lớn nhất mà ~S^K~ là xâu con của ~T~.

Ràng buộc

• 50% test tương ứng với độ dài xâu ~S,T~ không quá ~512~ kí tự.
• 50% test tương ứng với độ dài xâu ~S,T~ không quá ~10^6~ kí tự.

Ví dụ:

Input 1

pet
hopeforthebestbutpreparefortheworst 

Output 1

2