← 返回题目列表

Codeforces · 1295/C

C. 获取字符串

中文机器翻译题面 查看原题

给定两个由小写拉丁字母组成的字符串 $$$s$$$ 和 $$$t$$$。还有一个字符串 $$$z$$$ 最初是空的。您希望字符串 $$$z$$$ 等于字符串 $$$t$$$。您可以执行以下操作来实现此目的:将 $$$s$$$ 的任何子序列附加到字符串 $$$z$$$ 的末尾。子序列是可以通过删除零个或多个元素而不改变剩余元素的顺序从给定序列派生的序列。例如,如果 $$$z = ac$$$, $$$s = abcde$$$,则可以通过一次操作将 $$$z$$$ 转换为以下字符串:

1. $$$z = acace$$$(如果我们选择子序列$$$ace$$$);
2. $$$z = acbcd$$$(如果我们选择子序列$$$bcd$$$);
3. $$$z = acbce$$$(如果我们选择子序列$$$bce$$$)。

请注意,在此操作之后,字符串 $$$s$$$ 不会改变。

计算将字符串 $$$z$$$ 转换为字符串 $$$t$$$ 的最少此类操作数。

输入

第一行包含整数 $$$T$$$ ($$$1 \le T \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个由小写拉丁字母组成的字符串 $$$s$$$ ($$$1 \le |s| \le 10^5$$$)。

每个测试用例的第二行包含一个由小写拉丁字母组成的字符串 $$$t$$$ ($$$1 \le |t| \le 10^5$$$)。

保证输入中所有字符串$$$s$$$和$$$t$$$的总长度不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 将字符串 $$$z$$$ 转换为字符串 $$$t$$$ 的最少操作数。如果不可能,请打印$$$-1$$$。

示例

输入 #1

3
aabce
ace
abacaba
aax
ty
yyt

输出 #1

1
-1
3