문제

민혁이는 $0$과 $1$로만 이루어진 길이 $N$ ($1 \le N \le 2 \cdot 10^5$)의 비밀 문자열 $b_1b_2 \dots b_N$을 가지고 있다.

당신에게 주어진 $b$에 대한 유일한 정보는 길이가 $N-K+1$ ($1 \le K \le N$)인 이진 문자열 $r_1r_2 \dots r_{N-K+1}$이다. 여기서 $r_i$는 $b$에서 인덱스 $i$부터 시작하는 길이 $K$인 구간(윈도우)에 포함된 $1$의 개수를 $2$로 나눈 나머지이다.

민혁이의 비밀 문자열에 포함될 수 있는 $1$의 개수의 최솟값과 최댓값을 구하시오.

입력

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 10^3$)가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

첫째 줄에 $N$과 $K$가 공백으로 구분되어 주어진다.

둘째 줄에 이진 문자열 $r_1 \dots r_{N-K+1}$이 주어진다. 여기서 $r_i = \sum_{j=i}^{i+K-1} b_j \pmod 2$이다.

모든 테스트 케이스에 대한 $N$의 합은 $10^6$을 넘지 않는다.

출력

각 테스트 케이스마다 민혁이의 비밀 문자열에 포함될 수 있는 $1$의 개수의 최솟값과 최댓값을 공백으로 구분하여 출력한다.

예제 입력 1

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

예제 출력 1

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

제한

• 제한 1: $N \le 8$
• 제한 2: $K \le 8$이며, 모든 테스트 케이스에 대한 $N$의 합은 $10^4$를 넘지 않는다.
• 제한 3: 추가적인 제약 조건이 없다.