Per có một mảng ~a~ gồm ~n~ số nguyên. Per có thể thực hiện thao tác sau một số lần tùy ý (có thể không lần nào): chọn một chỉ số ~i~ (~1 \le i \le n~) và đổi dấu ~a_i~, tức gán ~a_i := -a_i~.

Số yêu thích của Per là ~m~, và Per muốn ~a_1 + a_2 + \cdots + a_m~ là nhỏ nhất trong tất cả các tổng tiền tố khác rỗng. Nói chính xác, với mọi ~k = 1, 2, \ldots, n~ phải có

~a_1 + a_2 + \cdots + a_k \ge a_1 + a_2 + \cdots + a_m.~

Lưu ý có thể tồn tại nhiều tổng tiền tố cùng nhỏ nhất; chỉ yêu cầu ~a_1 + \cdots + a_m~ là một trong số đó.

Hãy tìm số thao tác ít nhất cần thực hiện. Có thể chứng minh luôn tồn tại một dãy thao tác thỏa mãn.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~t~ — số bộ test. Mỗi bộ test gồm hai dòng:

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~m~ — độ dài mảng và số yêu thích của Per.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~.

Kết quả

In ra ~t~ dòng, dòng thứ ~i~ là số thao tác ít nhất của bộ test thứ ~i~.

Ví dụ

Đầu vào:

6
4 3
-1 -2 -3 -4
4 3
1 2 3 4
1 1
1
5 5
-2 3 -5 1 -20
5 2
-2 3 -5 -5 -20
10 4
345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873

Đầu ra:

1
1
0
0
3
4

Giải thích: Ở bộ test thứ nhất, đổi dấu ~a_4~ được mảng ~[-1, -2, -3, 4]~ với các tổng tiền tố ~[-1, -3, -6, -2]~; tổng ~a_1 + a_2 + a_3 = -6~ là nhỏ nhất.

Ở bộ test thứ hai, đổi dấu ~a_3~ được ~[1, 2, -3, 4]~ với các tổng tiền tố ~[1, 3, 0, 4]~.

Ở bộ test thứ ba và thứ tư, tổng ~a_1 + \cdots + a_m~ đã là nhỏ nhất, không cần thao tác nào.

Ở bộ test thứ năm, đổi dấu ~a_3~, ~a_2~ và ~a_5~ được ~[-2, -3, 5, -5, 20]~ với các tổng tiền tố ~[-2, -5, 0, -5, 15]~. Hai tổng ~a_1 + a_2 = -5~ và ~a_1 + a_2 + a_3 + a_4 = -5~ cùng nhỏ nhất, điều này được chấp nhận.

Giới hạn

• ~1 \le t \le 10^4~
• ~1 \le m \le n \le 2 \cdot 10^5~
• ~-10^9 \le a_i \le 10^9~
• Tổng ~n~ trên tất cả các bộ test không vượt quá ~2 \cdot 10^5~.