给定两个字符串 $$$s$$$ 和 $$$t$$$,每个字符串的长度为 $$$n$$$ 并由小写拉丁字母组成。您想让 $$$s$$$ 等于 $$$t$$$。
您可以对 $$$s$$$ 执行以下操作任意次来实现 —
- 选择$$$s$$$的任意子串,顺时针旋转一次,即如果选择的子串是$$$s[l,l+1...r]$$$,那么它就变成$$$s[r,l,l + 1 ... r - 1]$$$。 $$$s$$$ 的所有剩余字符保持在其位置。例如,在旋转子字符串 $$$[2,4]$$$ 时,字符串“abcde”变为“adbce”。
字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。
求将 $$$s$$$ 转换为 $$$t$$$ 所需的最少操作数,或者确定这是不可能的。
输入
输入的第一行包含一个整数 $$$t$$$ $$$(1\leq t \leq 2000)$$$ — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1\leq n \leq 2000)$$$ — 字符串的长度。
第二行和第三行分别包含字符串 $$$s$$$ 和 $$$t$$$。
所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。
输出
对于每个测试用例,输出将 $$$s$$$ 转换为 $$$t$$$ 的最小操作数。如果无法将 $$$s$$$ 转换为 $$$t$$$,则输出 $$$-1$$$。
示例
输入 #1
6 1 a a 2 ab ba 3 abc cab 3 abc cba 4 abab baba 4 abcc aabc
输出 #1
0 1 1 2 1 -1
注意
对于 $$$1$$$-st 测试用例,由于 $$$s$$$ 和 $$$t$$$ 相等,因此不需要应用任何操作。
对于$$$2$$$-nd测试用例,只需对整个字符串ab进行一次操作即可将其转换为ba。
对于$$$3$$$-rd测试用例,只需对整个字符串abc进行一次操作即可将其转换为cab。
对于第 $$$4$$$ 个测试用例,您需要应用两次操作:首先对整个字符串 abc 将其转换为 cab,然后对从第二个字符开始的长度为 $$$2$$$ 的子字符串将其转换为 cba。
对于第 $$$5$$$ 测试用例,只需对整个字符串 abab 执行一次操作即可将其转换为 baba。
对于第 $$$6$$$ 个测试用例,无法将字符串 $$$s$$$ 转换为 $$$t$$$。