All submissions for this problem are available.
Sourabh and Rishabh are enemies of each other and want to kill each other. Rishabh has lot of money . So he went to the shop to buy bullets but shopkeeper was a nerd he gave him a string conatining 0's and 1's where 1 refers to unused bullet and 0 refers to bullets that are already used.
Rishabh wants to buy as much bullets as he can but he doesnot want to pay for used bullets therefore he wants to collect bullets in such a way that no used bullets comes with the new bullets (he can start collecting bullet from anywhere in the string, and once he collects a bullet, he can collect bullets either from the left, or from the right without skipping any bullet and stops immediately when he reaches used bullet.) eg. if the string is 1010111011 then maximum number of bullets he can get without any used bullets are 3. Help him by giving him a program for that.
The first line of input contains T the total number of testcases and in each test case a string of 0's and 1's are given.
Output a single line maximum number of bullets he can buy without without taking any used bullets among them.
1 ≤ T ≤ 100
1 ≤ Length of the string ≤ 10^5
Input: 2 10011110111011 111110001110 Output: 4 5
Example case 1. He will first pick the 7th bullet then keep collecting bullets from its left upto 4th bullet.
Example case 2. He will first pick the 1st bullet then keep collecting bullets from its right upto 5th bullet.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYPY|
Fetching successful submissions