Xiaohong gave Xiaoming a string s containing only 0 and 1. Xiaohong wants to know the maximum interval [l, r] so that the number of '0' inside is a multiple of '1', or the number of '1' is a multiple of the number of '0'.
For the clumsy little red, she didn't want to know what the l of this largest interval is and what is r, she just wants to know the value of r-l+1.
For Xiao Ming, who has always loved Xiaohong, he must help Xiaohong find this value, but Xiao Ming is also very clumsy, so he found you.
Since S is too long, it can't be calculated by Xiao Ming, so please help he with programming to solve this problem.
这题太简单了就不翻译了
An integer T indicates the number of questions Xiao Hong gave to Xiao Ming. (1<=T<=20)
Each question contains a string s (1<=|s|<=1000)
Guarantee all problems ∑|s|<=5000.
Each question outputs a line of integers indicating the value of the maximum interval r-l+1. If there is no interval [l, r], then 0 is output.
3 01 101 1011010
2 3 6