A string 'S' of length L is called binary COUPLED if there exists at least one integer K (1 <= K <= L) such that the numbers of zero's in substring S[1,K-1] is equal to number of one's in substring S[K,L].(indexing starts from 1). Given a string Str of length M, find out number of such pairs of integers (X,Y) such that substring Str[X,Y] is Coupled,where 1<=X<=Y<=M.
1st line: An Integer T denoting the number of test cases.
Each test Case Contains: one string (no whitespaces). Each string only contains O and 1.
Output a single line containing the answer for this test case.
In the first test case coupled substrings are Str[1, 1] = 0 and Str[1, 2] = 01.
For the substring Str[1,1],you should choose k=1 then Str[1,k-1] = S[1,0] = "" (empty string) has 0 zeros and S[k,L] = S[1,1] = "0" has 0 ones.
Number of Test Cases T , 1 < T <= 100
Problem Setter : Vivek Bhatnagar