All Submissions


Background

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.

Input

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

Output a single line containing the answer for this test case.

Sample Input


3
01
10
0101011


Sample Output


2
2
23


Explanation

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.

Constraints

Number of Test Cases T , 1 < T <= 100

1<=|Str|<=100000

Problem Setter : Vivek Bhatnagar

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0