给定两个字符串 $$$s$$$ 和 $$$t$$$,长度相等 $$$n$$$。您可以一步操作交换字符串 $$$s$$$ 的任意两个相邻字符。
您需要找到使字符串 $$$s$$$ 按字典顺序小于字符串 $$$t$$$ 所需的最少操作数。
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。
输入
第一行输入包含一个整数 $$$q$$$ ($$$1 \le q \le 10\,000$$$):测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。
每个测试用例的第二行包含由 $$$n$$$ 小写英文字母组成的字符串 $$$s$$$。
每个测试用例的第三行包含由 $$$n$$$ 小写英文字母组成的字符串 $$$t$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行中打印使字符串 $$$s$$$ 按字典顺序小于字符串 $$$t$$$ 所需的最少操作数,或者如果不可能,则打印 $$$-1$$$。
示例
输入 #1
4 1 a a 3 rll rrr 3 caa aca 5 ababa aabba
输出 #1
-1 0 2 2