Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

REPROAD - Repair road

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

 


Added by:Yep Sheng
Date:2016-03-18
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C++ 4.3.2 CPP CPP14 JAVA

hide comments
2016-10-08 07:50:01
ENGLISH PLS
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.