问题描述

嘉言、伊芙琳和婉臣三个人在度假。 她们有一个隐藏的二进制字符串 $b_1b_2\ldots b_N$。关于 $b$ 的唯一信息是一个二进制串 $r_1r_2\ldots r_{N-K+1}$，其中 $r_i$ 表示 $b_i b_{i+1} \ldots b_{i+K-1}$ 这个字符串里 1 的个数除以 2 的余数。

请输出这个隐藏的二进制字符串 $b_1b_2\ldots b_N$ 包含的 1 的最少和最多数量。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^3$），表示测试用例的数量。 每个测试用例包含两行：

• 第一行：两个整数 $N, K$。
• 第二行：一个二进制字符串 $r_1\ldots r_{N-K+1}$。

保证所有测试用例的 $N$ 之和不超过 $10^6$。

输出格式

共 $T$ 行。 对于每个测试用例，输出隐藏的二进制字符串 $b_1b_2\ldots b_N$ 包含的 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 5
1 5
1 3
0 5

数据范围

• 对于 10% 的数据，$N \le 8$。
• 对于另外 20% 的数据，$K \le 8$，且所有测试用例的 $N$ 之和不超过 $10^4$。
• 对于 100% 的数据，$1 \le N \le 2 \times 10^5$，$1 \le K \le N$。