Debugging Question

In this question, the task is to debug the existing code to successfully execute all provided test files.

Problem Statement

Ana loves playing with binary strings(a string which contains only characters '0' and '1' are called binary strings) and associating it with some special qualities.

She discovers a property “Power” of binary strings which is denoted as the total number of pairs (i,j) in the given string such that the Substring S(i),S(i+1),S(i+2)….S(j-1),S(j) is magical. (1<= i <= j <= |S|)

Let’s say the frequency of characters ‘0’ and ‘1’ in a given binary string be f0 and f1 respectively. It is said to be magical if f0 is equal to the square of f1.

Help Ana find the “Power” of each binary string she has.

Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains a single string S.

Output

For each test case, print a single line containing one integer — the Power of the string S.

Constraints

1 ≤ T ≤ 10

1 ≤ |S| ≤ 10^5

Each character of S is '0' or '1'