Ghép xâu từ dãy con

Cho hai xâu $s$ và $t$ gồm các chữ cái Latin thường. Ban đầu có một xâu $z$ rỗng. Mỗi thao tác, bạn chọn một dãy con bất kỳ của $s$ và nối nó vào cuối xâu $z$. Xâu $s$ không thay đổi sau mỗi thao tác.

Dãy con của một xâu là xâu thu được bằng cách xoá đi không hoặc một số ký tự mà không thay đổi thứ tự các ký tự còn lại. Ví dụ, với $z$ = "ac" và $s$ = "abcde", sau một thao tác có thể nhận được $z$ = "acace" (chọn "ace"), $z$ = "acbcd" (chọn "bcd") hoặc $z$ = "acbce" (chọn "bce").

Hãy tính số thao tác ít nhất để $z$ trở thành $t$, hoặc cho biết điều đó là không thể.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $T$, số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng: dòng thứ nhất chứa xâu $s$, dòng thứ hai chứa xâu $t$.

Dữ liệu ra

• Với mỗi bộ dữ liệu, in ra một dòng chứa số thao tác ít nhất, hoặc $-1$ nếu không thể tạo được $t$.

Ràng buộc

• $1\le T\le 100$
• $1\le |s|,|t|\le {10}^5$
• Tổng độ dài của tất cả các xâu $s$ và $t$ trong một file dữ liệu không vượt quá $2·{10}^5$.
• Các xâu chỉ gồm chữ cái Latin thường.

Ví dụ