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).

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

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

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.