题目描述

鸠和 Gino 正在美食街寻找餐馆，面前有 $T$ 个餐馆，每个餐馆都有一块写满小写字母的霓虹灯牌。设灯牌上由 $n$ 个小写字母组成的字符串为 $s$，所有长度为 $k$ 的连续子串都对应餐馆中一道菜的名字。

霓虹城的餐馆有一个规矩：对于一个菜名 $t$，设其中每个小写字母的出现次数组成的可重集合为 $T = \{cnt_a, cnt_b, \cdots, cnt_z \}$，则这道菜的价格为 $\operatorname{mex}(T)$，即集合 $T$ 中最小未出现过的自然数。

为了根据钱包余额做出抉择，Gino 和鸠需要知道每个餐馆的菜品价格最小值和最大值。

输入格式

【本题有多组测试数据】

第一行包含一个正整数 $T$，代表餐馆数。

对于每个餐馆，第一行包含两个整数 $n,k$，分别代表字符串的长度与菜名的长度；第二行包含一个长度为 $n$ 的字符串 $s$，代表霓虹灯牌上的字符串。

输出格式

对于每个餐馆，输出一行两个整数，分别表示菜品价格的最大值与最小值。

输入样例

2
7 4
phigros
6 3
arcaea

输出样例

2 2
3 2

说明提示

数据范围

• $1 \leq T \leq 50$
• 对于每组测试数据，$1 \leq k \leq n \leq 5\times 10^5$
• 在每个测试点中，$n$ 的总和 $1 \leq \sum n \leq 5 \times 10^5$
• 保证 $s$ 全部由小写字母构成

本题采用捆绑测试。

• 特殊性质 A：$k=1$ 或 $k=n$
• 特殊性质 B：$s$ 全部由 a组成
• 特殊性质 C：$s$ 全部由 a 或 b 组成
• 特殊性质 D：$\operatorname{mex}(T) \leq 1$

注：编号为 $i$ 的大样例满足子任务 $i$ 的限制

本站补充：原套别：第 11 套 A 题。