HUST CLASS 14 160917

Vietnamese
Sau một trận động đất,
 nhiều con đường đã bị phá hủy. Mỗi con đường có một vài đoạn bị hư hỏng, nên phương tiện không thể di chuyển trên những đoạn đường này. Nhằm đảm bảo mạng lưới giao thông được thông suốt, chính phủ đã tiến hành sửa đường. Với mỗi đơn vị đường (1 block), chính phủ cần sử dụng 1 đơn vị tiền. Nếu con đường có M đoạn bị hỏng, thì chính phủ sẽ cần M đơn vị tiền. Tuy nhiên, có quá nhiều đoạn đường bị hỏng trong khi chính phủ chỉ có K đơn vị tiền dành cho việc sửa đường. Vậy với K đơn vị tiền, chính phủ muốn sửa con đường sao cho số đoạn đường liên tiếp mà phương tiện giao thông có thể di chuyển là lớn nhất.
Ví dụ, hình ảnh dưới đây minh họa 1 con đường với 11 đoạn, chúng có 4 đoạn bị hỏng được đánh dấu bằng các ô màu xám (đoạn 2, 3, 6 và 8).

Nếu họ chỉ có 2 đơn vị tiền cho việc sửa đường, để thu được đoạn đường liên tiếp dài nhất cho phương tiện giao thông di chuyển, chính phủ phải sửa 2 đoạn 6 và 8, khi đó phương tiện có thể di chuyển giữa đoạn 4 và 11, với độ dài đoạn đường là 8.

Cho trước trạng thái của 1 con đường, hãy in ra chiều dài lớn nhất của đoạn đường liên tiếp mà phương tiện giao thông có thể di chuyển sau khi sửa đường sử dụng K đơn vị tiền. Đáp án cho ví dụ nêu trên là 8.
Input
Tổng số lượng phép thử là T (1 <= T  <= 20) được cho trên dòng đầu tiên.
Mỗi phép thử được cho trên 2 dòng, dòng đầu tiên của mỗi phép thử là số lượng đoạn đường N (5 <= N <= 10000) của con đường và số tiền dành cho việc sửa đường K (0 <= K <= N), cách nhau bởi 1 dấu cách trắng. Dòng tiếp theo mô tả trạng thái của con đường, những đoạn bị hỏng có giá trị là '0' và những đoạn không bị hỏng là '1'. Các giá trị trên cùng 1 dòng được ngăn cách bởi 1 dấu cách trắng.
Output
Hãy in đáp án của mỗi phép thử trên 1 dòng. 
Sample




Input


Output




2
10 1
1 1 1 1 1 1 0 0 1 1
11 2
1 0 0 1 1 0 1 0 1 1   1


7
8





English
After the earthquake, many road were damaged. Each road has some blocks were damaged, so vehicles cannot move on these blocks. To ensure the traffic network is connected, they need to repair those roads. For each road, to repair 1 block, they need 1 unit of money. So if a road has M blocks are damaged, then they need M unit of money. However, too many roads were damaged, they only have K unit of money to repair a specific road. Then with K unit of money, they wish to repair the road such that the number of consecutive blocks that vehicles can move on is maximum.
For example, the following is a road with 11 blocks, there are 4 blocks need to repair are marked in gray color (block 2, 3, 6 and 8).

If they have only 2 unit of money to repair this road, to get maximum the number of consecutive blocks that vehicles can move on after repair, they must to repair the block 6 and 8, then the vehicles can move from block 4 to block 11, and the length is 8.
 
Given a status of road, print out the maximum consecutive blocks that vehicles can move on after repair with maximum K unit of money. The answer for the above example should be 8.
Input
The total number of test cases T (1  T ) will be given the in the first line.
Each test case will be given in the following 2 lines, the first line of each test case is a number of blocks of the road N (5 <= N <= 10000) and a number K (0 <= K <= N) separated by a space. The next line is the status of road, those blocks were damaged are indicated with '0' and those not are indicated with '1'. Adjacent blocks in the same line are separated with a blank space.
Output
Print the answer for each test case on 1 line.

 
 
Sample




Input


Output




2
10 1
1 1 1 1 1 1 0 0 1 1
11 2
1 0 0 1 1 0 1 0 1 1   1


7
8