提示: 欢迎访问OurACM平台。
Problem 2041 Checker

Accept: 120    Submit: 454
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Checker game is an interesting game. But now Bob is tired of playing with others, he wants to play by himself. The following are the rules of his games:

1. The chessboard is a straight line which has n lattices.

2. There is only one kind of chess.

3. In the initial state, there are some chesses in the chessboard. There would be at most one chess in each lattice.

4. One chess can be moved directly to the adjacent empty lattice.

5. Your can move m steps at most. You can stop any time before you use up m steps.

6. The final score you get is the length of the longest continuous empty lattice.

Now Bob want to get as high score as possible. Can you tell him the possible highest score? The following is one example when m equals to 3. The highest score you can get in this case is 6.

Input

The first line of the input contains an integer T(T≤100), indicating the number of test cases. Each case begins with two integers n(1≤n≤500) and m(1≤m≤n*n), the number of lattices and the steps you can move at most, and is followed by a 0-1 string of length n. Here, 0 indicates an empty lattice and 1 indicates a full one.

Output

For each test case, print a line containing the test case number (beginning with 1) and the possible highest score Bob can get.

Sample Input

2 4 1 1010 10 3 1000100010

Sample Output

Case 1: 2 Case 2: 6

Source

2011年全国大学生程序设计邀请赛(福州)

Submit  Back  Status  Discuss