Một xâu ~A~ được gọi là rút gọn của xâu ~B~ nếu ta có thể tạo ra ~A~ bằng cách xóa đi ~0~ hoặc nhiều ký tự trong ~B~ mà không thay đổi thứ tự các ký tự còn lại. Theo định nghĩa này, một xâu luôn là xâu rút gọn của chính nó.

Chẳng hạn:

• ac, ab, aa là các xâu rút gọn của aabc;
• d, aaa, ba không phải là xâu rút gọn của aabc.

Yêu cầu

Cho hai xâu ~S~ và ~T~ chỉ gồm các ký tự chữ cái thường trong bảng chữ cái tiếng Anh. Gọi ~T^n~ là xâu được tạo ra bằng cách nối ~n~ xâu ~T~ lại với nhau. Hãy tìm giá trị nhỏ nhất của ~n~ sao cho ~S~ là một xâu rút gọn của xâu ~T^n~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng 1: xâu ~S~ với độ dài ~|S|~ ~(1 \le |S| \le 10^6)~;
• Dòng 2: xâu ~T~ với độ dài ~|T|~ ~(1 \le |T| \le 10^5)~.

Dữ liệu đầu ra

Gồm một số nguyên là giá trị ~n~ nhỏ nhất sao cho ~S~ là xâu rút gọn của ~T~. Nếu không tồn tại giá trị ~n~ như vậy thì in ra ~-1~.

Ràng buộc dữ liệu

• 8% điểm dành cho các test có ~S~ và ~T~ chỉ chứa ký tự a;
• 13% điểm khác dành cho các test có ~|S|, |T| \le 100~;
• 21% điểm khác dành cho các test có ~|S| \le 10^4,\ |T| \le 100~;
• 34% điểm khác dành cho các test có ~|T| \le 1000~;
• 24% điểm còn lại không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

INPUT

caa
ac

OUTPUT

3

Giải thích: Ta có: ~T^1 = T =~ ac, ~T^2 =~ acac, ~T^3 =~ acacac; ~n = 3~ là giá trị nhỏ nhất để xâu ~S~ trở thành xâu rút gọn của ~T^n~.

Ví dụ 2

INPUT

cab
acca

OUTPUT

-1

Giải thích: Không tìm được ~n~ nào thoả mãn điều kiện.