D. Piza Removes the Letters
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Piza 扔给了你仅包含小写字母的字符串 $$$S$$$ ，请你先删除一个长为 $$$m$$$ 的子串，再任选 $$$k$$$ 个字符串中未删除的字符删除，求 $$$\sum_{i=0}^{25} (\text{cnt}(S,'a'+i))^2$$$ 的最小值。

其中 $$$\text{cnt}(S,x)$$$ 代表字符串 $$$S$$$ 中 $$$x$$$ 的出现次数。

如果从字符串 $$$S$$$ 的前面和后面删去任意个字母（可以为0）后得到字符串 $$$T$$$ ，则 $$$T$$$ 被称为 $$$S$$$ 的子串。

例如 "zbc" 是 "zbceyond" 的子串，"ntr"是"country"的子串，"piza"是"piza"的子串。

Input

输入第一行包含一个整数 $$$T\ (1 \le T \le 2\times 10^5)$$$ ，代表测试组数。

对于每组测试用例，第一行包含三个整数 $$$n,m,k$$$ $$$(1\le{n}\le{2\times{10^5}},0\le{m}\le{n},0\le{k}\le{n-m})$$$ ，分别代表字符串 $$$S$$$ 的长度，需要删除的子串长度和要删除的字母个数。

第二行包含一个长为 $$$n$$$ 的仅包含小写字母的字符串 $$$S$$$ 。

确保 $$$\sum n\le{5\times{10^5}}$$$ 。

Output

对于每组数据输出一个整数代表 $$$\sum_{i=0}^{25} (\text{cnt}(S,'a'+i))^2$$$ 的最小值。

Example
Input
1
11 3 4
abcaabcbbaa
Output
6