CF1778C.Flexible String

You have a string $a$ and a string $b$. Both of the strings have length $n$. There are at most $10$ different characters in the string $a$. You also have a set $Q$. Initially, the set $Q$ is empty. You can apply the following operation on the string $a$ any number of times:

• Choose an index $i$ ($1\leq i \leq n$) and a lowercase English letter $c$. Add $a_i$ to the set $Q$ and then replace $a_i$ with $c$.

For example, Let the string $a$ be "$\tt{abecca}$". We can do the following operations:

• In the first operation, if you choose $i = 3$ and $c = \tt{x}$, the character $a_3 = \tt{e}$ will be added to the set $Q$. So, the set $Q$ will be ${\tt{e}}$, and the string $a$ will be "$\tt{ab\underline{x}cca}$".
• In the second operation, if you choose $i = 6$ and $c = \tt{s}$, the character $a_6 = \tt{a}$ will be added to the set $Q$. So, the set $Q$ will be ${\tt{e}, \tt{a}}$, and the string $a$ will be "$\tt{abxcc\underline{s}}$".

You can apply any number of operations on $a$, but in the end, the set $Q$ should contain at most $k$ different characters. Under this constraint, you have to maximize the number of integer pairs $(l, r)$ ($1\leq l\leq r \leq n$) such that $a[l,r] = b[l,r]$. Here, $s[l,r]$ means the substring of string $s$ starting at index $l$ (inclusively) and ending at index $r$ (inclusively).

你有两个字符串 $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$ 种不同的字符。在此约束下，你需要最大化满足 $a[l,r] = b[l,r]$ 的整数对 $(l, r)$（其中 $1 \leq l \leq r \leq n$）的个数。此处 $s[l,r]$ 表示字符串 $s$ 从下标 $l$（含）开始、到下标 $r$（含）结束的子串。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line contains two integers $n$ and $k$ ($1\leq n \leq 10^5$, $0\leq k\leq 10$) — the length of the two strings and the limit on different characters in the set $Q$.

The second line contains the string $a$ of length $n$. There is at most $10$ different characters in the string $a$.

The last line contains the string $b$ of length $n$.

Both of the strings $a$ and $b$ contain only lowercase English letters. The sum of $n$ over all test cases doesn't exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print a single integer in a line, the maximum number of pairs $(l, r)$ satisfying the constraints.

对于每个测试用例，在一行中输出一个整数，表示满足约束条件的数对 $(l, r)$ 的最大数量。

In the first case, we can select index $i = 3$ and replace it with character $c = \tt{d}$. All possible pairs $(l,r)$ will be valid.

In the second case, we can't perform any operation. The $3$ valid pairs $(l,r)$ are:

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}$".

In the third case, we can choose index $2$ and index $3$ and replace them with the characters $\tt{c}$ and $\tt{d}$ respectively. The final set $Q$ will be ${\tt{b}}$ having size $1$ that satisfies the value of $k$. All possible pairs $(l,r)$ will be valid.

在第一种情况下，我们可以选择索引 $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)$ 均有效。