题目描述

Bessie 有一个隐藏的二进制串 \(b_1b_2\dots b_N\)，满足 \(1 \le N \le 2 \cdot 10^5\)。

你并不知道这个串本身，只知道另一个二进制串：

\(r_1r_2\dots r_{N-K+1}\)

其中 \(1 \le K \le N\)，并且 \(r_i\) 表示长度为 \(K\)、左端点为 \(i\) 的窗口中，1 的个数对 \(2\) 取模后的结果，也就是：

\(r_i \equiv \sum_{j=i}^{i+K-1} b_j \pmod 2\)

请你求出：原串中 1 的个数最少可能是多少，最多可能是多少。

输入格式

第一行包含整数 \(T\)，表示测试组数，满足 \(1 \le T \le 10^3\)。

每组测试数据格式如下：

• 第一行两个整数 \(N, K\)
• 第二行一个长度为 \(N-K+1\) 的二进制串 \(r\)

保证所有测试数据中 \(N\) 的总和不超过 \(10^6\)。

输出格式

对于每组测试数据，输出一行两个整数，分别表示原串中 1 的个数的最小值与最大值。

样例

输入

7
5 1
10011
5 2
1001
5 3
100
5 5
0
5 5
1
4 4
1
5 2
0000

输出

3 3
2 3
1 4
0 4
1 5
1 3
0 5

说明

对于第一组数据，\(K=1\)，因此 \(r=b\)，所以 1 的个数唯一确定为 \(3\)。

对于第二组数据，满足条件的 \(b\) 有两种：

• 10001，其中有 \(2\) 个 1
• 01110，其中有 \(3\) 个 1

数据范围

• 输入 2：\(N \le 8\)
• 输入 3-4：\(K \le 8\)，且所有测试数据中 \(N\) 的总和不超过 \(10^4\)
• 输入 5-11：无额外限制

命题信息

原题命题：Benjamin Qi