这个问题的灵感来自于花衣魔笛手的故事。在受到 Hooli 的压缩竞争对手 Nucleus 的挑战后,Richard 通宵达旦地发明了一种新的压缩方法:中出(middle-out)。
给定两个字符串 $$$s$$$ 和 $$$t$$$,长度相同 $$$n$$$。他们的字符从左到右(即从开始到结束)编号为 $$$1$$$ 到 $$$n$$$。
在一次移动中,您可以执行以下一系列操作:
- 选择任何有效索引 $$$i$$$ ($$$1 \le i \le n$$$),
- 将 $$$s$$$ 的第 $$$i$$$ 个字符从其位置移动到字符串的开头,或将 $$$s$$$ 的第 $$$i$$$ 个字符从其位置移动到字符串的末尾。
请注意,移动不会改变字符串 $$$s$$$ 的长度。您只能对字符串 $$$s$$$ 应用移动。
例如,如果一步$$$s=$$$"test",你可以获得:
- 如果 $$$i=1$$$ 并且移到开头,则结果为“test”(字符串不变),
- 如果 $$$i=2$$$ 并且移至开头,则结果为“etst”,
- 如果 $$$i=3$$$ 并且移至开头,则结果为“stet”,
- 如果 $$$i=4$$$ 并且移到开头,则结果是“ttes”,
- 如果 $$$i=1$$$ 并且移至末尾,则结果为“estt”,
- 如果 $$$i=2$$$ 并且移动到末尾,那么结果是“tste”,
- 如果 $$$i=3$$$ 并且移动到末尾,那么结果是“tets”,
- 如果 $$$i=4$$$ 并且移至末尾,则结果为“test”(字符串不变)。
您想让字符串 $$$s$$$ 等于字符串 $$$t$$$。您需要的最少移动次数是多少?如果无法将 $$$s$$$ 转换为 $$$t$$$,则打印 -1。
输入
第一行包含整数 $$$q$$$ ($$$1 \le q \le 100$$$) — 输入中独立测试用例的数量。
每个测试用例都以三行给出。测试用例的第一行包含 $$$n$$$ ($$$1 \le n \le 100$$$) — 字符串 $$$s$$$ 和 $$$t$$$ 的长度。第二行包含$$$s$$$,第三行包含$$$t$$$。字符串 $$$s$$$ 和 $$$t$$$ 的长度为 $$$n$$$ 并且仅包含小写拉丁字母。
测试中对 $$$n$$$ 的总和没有限制(即允许输入 $$$q=100$$$ 且所有 $$$n=100$$$ 都是允许的)。
输出
对于每个测试,打印将 $$$s$$$ 转换为 $$$t$$$ 所需的最小可能移动次数,如果不可能,则打印 -1。
示例
输入 #1
3 9 iredppipe piedpiper 4 estt test 4 tste test
输出 #1
2 1 2
输入 #2
4 1 a z 5 adhas dasha 5 aashd dasha 5 aahsd dasha
输出 #2
-1 2 2 3
注意
在第一个示例中,最佳答案之一的移动是:
- 第一个测试用例 $$$s=$$$"iredppipe", $$$t=$$$"piedpiper": "iredppipe" $$$\rightarrow$$$ "iedppiper" $$$\rightarrow$$$ "piedpiper";
- 对于第二个测试用例 $$$s=$$$"estt", $$$t=$$$"test": "estt" $$$\rightarrow$$$ "test";
- 对于第三个测试用例 $$$s=$$$"tste", $$$t=$$$"test": "tste" $$$\rightarrow$$$ "etst" $$$\rightarrow$$$ "test"。