Xâu rút gọn

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”.

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 (nhập từ bàn phím/thiết bị vào chuẩn)

• 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$).

Kết quả (ghi ra màn hình/thiết bị ra chuẩn)

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

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