题目描述

给定两个由小写字母组成且长度相等的字符串 A 和 B。

你可以对 A 进行零次或多次以下操作：

• 将 A 的开头字符移动到末尾。

请求出使 A = B 所需的最小操作次数。

但是，如果无论如何操作都无法使 A = B，请改为输出 -1。

共有 $T$ 个测试用例，请对每个测试用例求解。

输入格式

第一行一个整数 $T$，表示测试用例组数。接下来对于每组测试样例：

第一行一个字符串，表示字符串 A。

第二行一个字符串，表示字符串 B。

输出格式

对于每组测试样例，输出一行一个整数，表示使 A = B 所需的最小操作次数。如果无论如何操作都无法使 A = B，则输出 -1。

样例

5
babaaab
baaabba
aaa
bbb
ababa
ababa
abab
aabb
baaaabbabbbaaaaaabababbabbaaab
babbaaabbaaaabbabbbaaaaaababab

2
-1
0
-1
22

样例1解释

此输入包含 $5$ 个测试用例。

• 对于第 $1$ 个测试用例：A = babaaab，B = baaabba。对 A 进行 $2$ 次操作后，A 的变化为：babaaab → abaaabb → baaabba，此时 A = B。
• 对于第 $2$ 个测试用例：无论进行多少次操作，都无法将 aaa 变为 bbb。
• 对于第 $3$ 个测试用例：初始时 A 与 B 已相等。

数据范围

对于 $30\%$ 的数据，A 和 B 是仅由两种小写字母组成的字符串。

对于另外 $30\%$ 的数据，所有测试用例的字符串 A 和 B 的长度总和不超过 $5000$，即 $Sum (|A| + |B|) \le 5000$。

对于 $100\%$ 的数据，$1 ≤ T ≤ 10000$，$A$ 和 $B$ 是由小写字母组成的字符串，$2 ≤ |A| = |B| ≤ 10^6$，所有测试用例的字符串 A 的长度总和不超过 $10^6$。