#P9644. [SNCPC2019] Turn It Off
[SNCPC2019] Turn It Off
题目描述
It's already 21:30 now, and it's time for BaoBao to go to bed. To ensure his sleeping quality, BaoBao decides to turn all the lights in his bedroom off.
There are lights, numbered from 1 to , arranged in a row in BaoBao's bedroom. Each time BaoBao can select an integer and turn all the lights numbered from to (both inclusive) off, where is a predefined positive integer. Note that each time the value of must be the same.
Given the initial status of all the lights, please help BaoBao determine the smallest possible so that he can turn all the lights off within times.
输入格式
There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:
The first line contains two integers and ().
The second line contains a string (, ) indicating the initial status of the lights. Let be the -th character in , if then the -th light is initially on, otherwise it's initially off. It's guaranteed that there is at least one `1· in .
It's guaranteed that the sum of of all test cases will not exceed .
输出格式
For each test case output one line containing one integer, indicating the smallest possible .
2
10 4
0101011111
3 1
010
3
1