Jit and bitstream
Problem
You are given a binary string consisting of 0's and 1's. You need to flip exactly 1 bit and find the maximum number of consecutive 1's possible. A flip operation is defined as converting a bit to 0 if it is 1 and vice versa.
Input:
First line of input contains a integer t denoting number of test cases. First and only line of each test case contains a binary string s.
Output:
For each test case print the answer on a new line.
Constraints:
1≤t≤50
1≤|s|≤106
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation
Of all the possibilities, flipping 4th bit to 1 gives maximum length of consecutive 1's.
