Bessie có một chuỗi nhị phân bí mật ~b_1, b_2, \ldots, b_N~ ~(1 \le N \le 2 \cdot 10^5)~.

Thông tin duy nhất bạn biết về chuỗi ~b~ là một chuỗi nhị phân ~r_1, r_2, \ldots, r_{N-K+1}~ ~(1 \le K \le N)~.

Trong đó, ~r_i~ là phần dư khi chia số lượng ký tự 1 trong đoạn có độ dài ~K~ bắt đầu tại vị trí ~i~ của chuỗi ~b~ cho ~2~.

Cụ thể:

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

Yêu cầu: Xác định số lượng ký tự 1 nhỏ nhất và lớn nhất có thể có trong chuỗi nhị phân bí mật ~b~.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~T~ ~(1 \le T \le 10^3)~, là số bộ test.
• Mỗi bộ test gồm:
  • Dòng đầu tiên chứa hai số nguyên ~N, K~.
  • Dòng thứ hai chứa chuỗi nhị phân ~r~ có độ dài ~N-K+1~.

Đảm bảo: Tổng ~N~ trên tất cả các bộ test không vượt quá ~10^6~.

Dữ liệu ra

Với mỗi bộ test, in ra hai số nguyên trên một dòng:

• Số lượng ký tự 1 nhỏ nhất có thể có trong chuỗi ~b~.
• Số lượng ký tự 1 lớn nhất có thể có trong chuỗi ~b~.

Hai số được phân cách bởi một dấu cách.

Ví dụ

Input

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

Output

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

Giải thích

Test 1:

Vì ~K = 1~, mỗi cửa sổ chỉ chứa một ký tự, do đó ~r = b~.

Chuỗi 10011 có đúng ~3~ ký tự 1, nên kết quả là 3 3.

Test 2:

Có hai chuỗi ~b~ thỏa mãn:

• 10001: chứa ~2~ ký tự 1.
• 01110: chứa ~3~ ký tự 1.

Vì vậy, số lượng ký tự 1 nhỏ nhất là ~2~ và lớn nhất là ~3~.

Kết quả là 2 3.

Giới hạn

• Subtask 1 (Test 2): ~N \le 8~.
• Subtask 2 (Test 3–4): ~K \le 8~ và tổng ~N~ trên tất cả các bộ test không vượt quá ~10^4~.
• Subtask 3 (Test 5–11): Không có ràng buộc bổ sung.