Bessie has a hidden binary string b1b2…bN(1≤N≤2⋅105). The only information about b you are given is a binary string r1r2…rN−K+1 (1≤K≤N), where ri is the remainder when the number of ones in the length-K window of b with leftmost index i is divided by two.
Output the minimum and maximum possible numbers of ones in Bessie's hidden binary string.
INPUT FORMAT (input arrives from the terminal / stdin):
There are T (1≤T≤103) independent test cases to be solved. Each test is specified by the following:
The first line contains N and K.
The second line contains the binary string r1…rN−K+1, where 
(mod2).
It is guaranteed that the sum of N over all tests does not exceed 106.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, output the minimum and maximum possible numbers of ones in Bessie's hidden binary string, separated by a single space.
SAMPLE INPUT:
7
5 1
10011
5 2
1001
5 3
100
5 5
0
5 5
1
4 4
1
5 2
0000
SAMPLE OUTPUT:
3 3
2 3
1 4
0 4
1 5
1 3
0 5
For the first test case, K=1 means that r=b, and the number of ones in r is 3.
For the second test case, there are two possibilities for b: 10001 and 01110, having 2 and 3 ones, respectively.
SCORING:
Input 2: N≤8
Inputs 3-4: K≤8 and the sum of N over all tests does not exceed 104.
Inputs 5-11: No additional constraints.
Problem credits: Benjamin Qi