您有一个字符串 $$$a$$$ 和一个字符串 $$$b$$$。两个字符串的长度都是$$$n$$$。字符串 $$$a$$$ 中最多有 $$$10$$$ 不同的字符。您还有一套$$$Q$$$。最初,集合 $$$Q$$$ 是空的。您可以对字符串 $$$a$$$ 应用以下操作任意次:
- 选择索引 $$$i$$$ ($$$1\leq i \leq n$$$) 和小写英文字母 $$$c$$$。将 $$$a_i$$$ 添加到集合 $$$Q$$$ 中,然后将 $$$a_i$$$ 替换为 $$$c$$$。
例如,让字符串 $$$a$$$ 为“$$$\tt{abecca}$$$”。我们可以进行以下操作:
- 在第一个操作中,如果您选择 $$$i = 3$$$ 和 $$$c = \tt{x}$$$,则字符 $$$a_3 = \tt{e}$$$ 将被添加到集合 $$$Q$$$ 中。因此,集合 $$$Q$$$ 将是 $$$\{\tt{e}\}$$$,字符串 $$$a$$$ 将是“$$$\tt{ab\underline{x}cca}$$$”。
- 在第二个操作中,如果您选择 $$$i = 6$$$ 和 $$$c = \tt{s}$$$,则字符 $$$a_6 = \tt{a}$$$ 将被添加到集合 $$$Q$$$ 中。因此,集合 $$$Q$$$ 将是 $$$\{\tt{e}, \tt{a}\}$$$,字符串 $$$a$$$ 将是“$$$\tt{abxcc\underline{s}}$$$”。
你可以对$$$a$$$进行任意数量的操作,但最终,集合$$$Q$$$最多应该包含$$$k$$$个不同的字符。在此约束下,您必须最大化整数对 $$$(l, r)$$$ ($$$1\leq l\leq r \leq n$$$) 的数量,使得 $$$a[l,r] = b[l,r]$$$。这里,$$$s[l,r]$$$表示字符串$$$s$$$中从索引$$$l$$$(含)开始到索引$$$r$$$(含)结束的子串。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\leq n \leq 10^5$$$, $$$0\leq k\leq 10$$$) - 两个字符串的长度以及集合 $$$Q$$$ 中不同字符的限制。
第二行包含长度为 $$$n$$$ 的字符串 $$$a$$$。字符串 $$$a$$$ 中最多有 $$$10$$$ 个不同字符。
最后一行包含长度为 $$$n$$$ 的字符串 $$$b$$$。
字符串 $$$a$$$ 和 $$$b$$$ 均仅包含小写英文字母。所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,在一行中打印一个整数,满足约束的最大对数 $$$(l, r)$$$ 。
示例
输入 #1
6 3 1 abc abd 3 0 abc abd 3 1 xbb xcd 4 1 abcd axcb 3 10 abc abd 10 3 lkwhbahuqa qoiujoncjb
输出 #1
6 3 6 6 6 11
注意
在第一种情况下,我们可以选择索引 $$$i = 3$$$ 并将其替换为字符 $$$c = \tt{d}$$$。所有可能的对 $$$(l,r)$$$ 将有效。
在第二种情况下,我们无法执行任何操作。 $$$3$$$ 有效对 $$$(l,r)$$$ 为:
1. $$$a[1,1] = b[1,1] =$$$ "$$$\tt{a}$$$",
2. $$$a[1,2] = b[1,2] =$$$ "$$$\tt{ab}$$$",
3. $$$a[2,2] = b[2,2] =$$$“$$$\tt{b}$$$”。
在第三种情况下,我们可以选择索引$$$2$$$和索引$$$3$$$并将它们分别替换为字符$$$\tt{c}$$$和$$$\tt{d}$$$。最终集合$$$Q$$$将为$$$\{\tt{b}\}$$$,其大小为$$$1$$$,满足$$$k$$$的值。所有可能的对 $$$(l,r)$$$ 将有效。