### 问题描述 小然是一位著名的密码学家，他在研究一种神秘的二进制串 $S$。他发现，如果一个二进制串中，0 的数量和 1 的数量之差的绝对值越小，这个二进制串就越具有神秘性质。他称这个差的绝对值为二进制串的"坏度"。 现在，小然想要将这个二进制串 $S$ 划分为 $K$ 个不想交的子序列（其中一些子序列可能为空），使得所有子序列的"坏度"的最大值尽可能小。你能帮助他解决这个问题吗？ 请注意，子序列是通过从原串中删除一些字符（可能一个也不删除），但不改变剩余字符的相对位置得到的。 ### 输入格式 输入的第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例包含两行。第一行包含两个整数 $N$ 和 $K$，分别表示二进制串的长度和要划分的子序列的数量。第二行包含一个长度为 $N$ 的二进制串 $S$。 ### 输出格式 对于每个测试用例，输出一行，包含一个整数，表示所有子序列的"坏度"的最大值的最小可能值。 ### 样例输入 ```text 3 7 5 1010100 4 1 1100 6 2 101111 ``` ### 样例输出 ```text 1 0 2 ``` ### 说明 在第一个测试用例中，我们可以将二进制串划分为两个子序列，例如 "1010" 和 "101"，此时所有子序列的"坏度"的最大值是 $1$。 ### 评测数据范围 $1 \leq T \leq 1000$。 $1 \leq N \leq 2 \times 10^5$，$1 \leq K \leq 10^9$。 二进制串 $S$ 只包含 '0' 和 '1'。 所有测试用例中，$N$ 的总和不超过 $2 \times 10^5$。