All strings in Chefland are beautiful because they are binary strings (a binary string contains only characters '0' and '1'). The beauty of a binary string $S$ is defined as the number of pairs $(i, j)$ ($1 \le i \le j \le |S|$) such that the substring $S_i, S_{i+1}, \ldots, S_j$ is special.
For a binary string $U$, let's denote the number of occurrences of the characters '1' and '0' in $U$ by $cnt_1$ and $cnt_0$ respectively; then, $U$ is special if $cnt_0 = cnt_1 \cdot cnt_1$.
Today, Chef's friend Araspa is celebrating her birthday. Chef wants to give Araspa the most beautiful binary string he can find. Currently, he is checking out binary strings in a shop, but he needs your help to calculate their beauties. Tell Chef the beauty of each binary string he gives you.

-----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 beauty of the string $S$.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le |S| \le 10^5$
- each character of $S$ is '0' or '1'

-----Example Input-----
2
010001
10

-----Example Output-----
4
1

-----Explanation-----
Example case 1: The special substrings correspond to $(i, j) = (1, 2), (1, 6), (2, 3), (5, 6)$.

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for _ in range(t):
 s = input()
 pref = [0]*len(s)
 if s[0]=="1":
  pref[0]+=1
 for i in range(1,len(s)):
  if s[i]=="1":
   pref[i]+=1
  pref[i]=pref[i]+pref[i-1]
 k=1
 cnt=0
 while (k+k*k)<=len(s):
  r = k+k*k
  i=r-1
  while i<len(s):
   if (i-r)>=0:
    if pref[i]-pref[i-r]==k:
     cnt+=1
     i+=1
    else:
     i+=abs(k-(pref[i]-pref[i-r]))
     
   else:
    if pref[i]==k:
     cnt+=1
     i+=1
    else:
     i+=abs(k-(pref[i]))
  k+=1
 print(cnt)

# cook your dish here
for i in range(int(input())):
 s=input()
 n=len(s)
 one=[0]*(n+1) #number of ones from first place to i-th place
 for i in range(n):
  if s[i]=='1':
   one[i+1]=one[i]+1
  else:
   one[i+1]=one[i]
 ans=0
 i=1
 r=2 #r for range in interval r=i+i**2
 while r<=n:
  r=i+i**2
  j=0
  while j<=n-r:
   if one[j+r]-one[j]==i:
    ans+=1
    j+=1
   else:
    j+=abs(i-(one[j+r]-one[j]))
  i+=1
 print(ans)



# cook your dish here
for i in range(int(input())):
 s=input()
 n=len(s)
 one=[0]*(n+1) #number of ones from first place to i-th place
 for i in range(n):
  if s[i]=='1':
   one[i+1]=one[i]+1
  else:
   one[i+1]=one[i]
 ans=0
 i=1
 r=2 #r for range in interval r=i+i**2
 while r<=n:
  r=i+i**2
  j=0
  while j<=n-r:
   if one[j+r]-one[j]==i:
    ans+=1
    j+=1
   else:
    j+=abs(i-(one[j+r]-one[j]))
  i+=1
 print(ans)


try:
 for i in range(int(input())):
  s = input()
  n = len(s)
  count = 0
  ones = [0]*(n+1)
  for i in range(n):
   if s[i]=='1':
    ones[i+1] = ones[i]+1
   else:
    ones[i+1] = ones[i]
  i=1
  r = 2
  while r<=n:
   r = i+i*i
   j = 0
   while j<=n-r:
    if ones[j+r]-ones[j]==i:
     count+=1
     j+=1
    else:
     j+=abs(i-(ones[j+r]-ones[j]))
   i+=1
  print(count)
except:
 pass


for i in range(int(input())):
 s=input()
 n=len(s)
 one=[0]*(n+1) #number of ones from first place to i-th place
 for i in range(n):
  if s[i]=='1':
   one[i+1]=one[i]+1
  else:
   one[i+1]=one[i]
 ans=0
 i=1
 r=2 #r for range in interval r=i+i**2
 while r<=n:
  r=i+i**2
  j=0
  while j<=n-r:
   if one[j+r]-one[j]==i:
    ans+=1
    j+=1
   else:
    j+=abs(i-(one[j+r]-one[j]))
  i+=1
 print(ans)


for i in range(int(input())):
 s=input()
 one=[0]*(len(s)+1) #number of ones from first place to i-th place
 for i in range(len(s)):
  if s[i]=='1':
   one[i+1]=one[i]+1
  else:
   one[i+1]=one[i]
 ans=0
 i=1
 r=2 #r for range in interval r=i+i**2
 while r<=len(s):
  r=i+i**2
  j=0
  while j<=len(s)-r:
   if one[j+r]-one[j]==i:
    ans+=1
    j+=1
   else:
    j+=abs(i-(one[j+r]-one[j]))
  i+=1
 print(ans)

# cook your dish here
from sys import stdin
def sin():
 return stdin.readline()

def ans(s):
 c=0
 for i in range(len(s)):
  for j in range(i,len(s)):
   d=s[i:j+1]
   a=d.count("0")
   b=d.count("1")
   if a==b*b:
    c+=1
 return(c)

test=int(sin())
for _ in range(test):
 s=input()
 x=1
 ans=0
 n=len(s)
 te=[0]*(n+1)
 for i in range(1,n+1):
  te[i]+=(te[i-1]+int(s[i-1]))
 ps=te[0]
 l=x*x+x
 while l<=n:
  i=0
  while i<=n-l:
   j=i+l
   cnt1=te[j]-te[i]
   if cnt1==x:
    ans+=1
    i+=1
   else:
    i+=abs(x-cnt1)
  x+=1
  l=x*x+x
 print(ans)

# cook your dish here
from sys import stdin
def sin():
 return stdin.readline()

def ans(s):
 c=0
 for i in range(len(s)):
  for j in range(i,len(s)):
   d=s[i:j+1]
   a=d.count("0")
   b=d.count("1")
   if a==b*b:
    c+=1
 return(c)

test=int(sin())
for _ in range(test):
 s=input()
 x=1
 ans=0
 n=len(s)
 te=[0]*(n+1)
 for i in range(1,n+1):
  te[i]+=(te[i-1]+int(s[i-1]))
 ps=te[0]
 l=x*x+x
 while l<=n:
  i=0
  while i<=n-l:
   j=i+l
   cnt1=te[j]-te[i]
   if cnt1==x:
    ans+=1
    i+=1
   else:
    i+=abs(x-cnt1)
  x+=1
  l=x*x+x
 print(ans)


cnt1_max = 315
arr_size = [None]*(cnt1_max)
for i in range(1, cnt1_max+1):
 arr_size[i-1] = (i*(i+1), i)

t = int(input())
for _t in range(t):
 s = input()
 n = len(s)
 tot1 = [0]*(n+1)
 for i in range(1, n + 1):
  if s[i - 1] == '1':
   tot1[i] = tot1[i - 1] + 1
  else:
   tot1[i] = tot1[i - 1]

 beauty = 0
 for size, cnt in arr_size:
  i = 0
  limit = n-size
  while i < limit + 1:
   cnt1 = tot1[i + size] - tot1[i]
   if cnt1 == cnt:
    beauty += 1
    i += 1
   else:
    i += abs(cnt1-cnt)
 print(beauty)


for i in range(int(input())):
 s=input()
 one=[0]
 for i in range(len(s)):
  one+=[one[-1]]
  if s[i]=='1':
   one[-1]+=1
 ans=0
 i=1
 r=2
 while r<=len(s):
  r=i+i**2
  j=0
  while j<=len(s)-r:
   if one[j+r]-one[j]==i:
    ans+=1
    j+=1
   else:
    j+=abs(i-(one[j+r]-one[j]))
  i+=1
 print(ans)


t = int(input())
for k in range(t):
 s = input().strip()
 n = len(s)
 dp = [0]
 for i in s:
  if i == '1':
   dp.append(dp[-1]+1)
  else:
   dp.append(dp[-1])
 d = 1
 ans = 0
 l = d * d + d
 while l <= n:
  i = 0
  while i <= n - l:  # for i in range(0, n - l + 1):
   j = i + l
   cnt1 = dp[j] - dp[i]
   if cnt1 == d:
    ans += 1
    i += 1
   else:
    i += abs(d - cnt1)
    # print(i, j)
  d += 1
  l = d * d + d
 print(ans)



t = int(input())
for k in range(t):
 s = input().strip()
 n = len(s)
 dp = [0]
 for i in s:
  if i == '1':
   dp.append(dp[-1]+1)
  else:
   dp.append(dp[-1])
 d = 1
 ans = 0
 l = 2
 while l <= n:
  i = 0
  while i <= n - l:  # for i in range(0, n - l + 1):
   if dp[i+l] - dp[i] == d:
    ans += 1
    i += 1
   else:
    i += abs(d - (dp[i+l] - dp[i]))
  d += 1
  l = d * d + d
 print(ans)


for i in range(int(input())):
 s=input()
 one=[0]
 for i in range(len(s)):
  one+=[one[-1]]
  if s[i]=='1':
   one[-1]+=1
 ans=0
 i=1
 r=2
 while r<=len(s):
  r=i+i**2
  j=0
  while j<=len(s)-r:
   if one[j+r]-one[j]==i:
    ans+=1
    j+=1
   else:
    j+=abs(i-(one[j+r]-one[j]))
  i+=1
 print(ans)

compu=[(x*(x+1),x) for x in range(1,316)]
t=int(input())
for i in range(t):
 s=list(map(int,input().strip()))
 count=0
 #find prefix sum of 0s
 arr=[0]
 n=len(s)
 for i in range(1,n+1):
  arr.append(arr[i-1]+s[i-1])
 for i,a in compu:
  #count first i length substring
  if(i>n):
   break
  s1=arr[i]
  s0=i-s1
  if(s0==s1*s1):
   count+=1
  j=1
  while(j<(n-i+1)):
   s1=arr[i+j]-arr[j]
   s0=i-s1
   if(s0==s1*s1):
    count+=1
    j+=1
   else:
    j+=abs(a-s1)
 print(count)

# cook your dish here
t = int(input())

def length(x):
 return x**2 + x

def is_valid(count_0, count_1):
 return count_0 == count_1 ** 2

while t:
 t -= 1
 inputs = input()
 counts_1 = []
 n = len(inputs)
 cnt = 0
 for i in range(n):
  if inputs[i] == '1':
   cnt += 1
  counts_1.append(cnt)
 del i
 res = 0
 a = 1
 x = length(a)
 while x <= n:
  if is_valid(x - counts_1[x-1], counts_1[x-1]):
   res += 1
  i = x
  while i <= n-1:
   cnt_1 = counts_1[i] - counts_1[i-x]
   cnt_0 = x - cnt_1
   if is_valid(cnt_0, cnt_1):
    res += 1
    i += 1
   else:
    i += abs(a - cnt_1)

  a += 1
  x = length(a)
 print(res)


dic={}
for i in range(1,316):
 dic[i-1]=(i*(i+1),i)

t=int(input())
for _ in range(t):
 arr=list(map(int,input().rstrip()))
 n=len(arr)
 for i in range(1,n):
  arr[i]+=arr[i-1]
 arr.append(0)
 ans=0
 for length,cnt1 in dic.values():
  i=0
  while(i+length-1<n):
   real_cnt1=arr[i+length-1]-arr[i-1]
   if(real_cnt1==cnt1):
    ans+=1
    i+=1
   else:
    i+=abs(cnt1-real_cnt1)

 print(ans)

for _ in range(int(input())):
 s = input()
 a = []
 a.append(0)
 count = 1
 for i in s:
  if i=='1':
   a.append(a[-1]+1)
  else:
   a.append(a[-1])
  count+=1
 ans = 0
 i=1
 r=2
 while r<count:
  j=0
  while j<count-r:
   if a[j+r]-a[j]==i:
    ans+=1
    j+=1
   else:
    j+=abs(i-(a[j+r]-a[j]))
  i+=1
  r=i+i**2
 print(ans)

cnt1_max = 315
arr_size = [None]*cnt1_max
for i in range(1, cnt1_max+1):
 arr_size[i-1] = (i*(i+1), i)

#print(arr_size)
t = int(input())
for _t in range(t):
 s = input().strip()
 n = len(s)
 tot1 = [0]*(n+1)
 for i in range(1, n+1):
  if s[i-1] == '1':
   tot1[i] = tot1[i-1] + 1
  else:
   tot1[i] = tot1[i-1]
 #print(tot1)
 beauty = 0
 for size, cnt in arr_size:
  i = 0
  limit = n - size
  while i < limit+1:
   cnt1 = tot1[i+size] - tot1[i]
   #print(i,i+size,cnt1,cnt)
   if cnt1 == cnt:
    beauty += 1
    i+=1
   else:
    i += abs(cnt1-cnt)
 print(beauty)

cnt1_max = 315
arr_size = [None]*cnt1_max
for i in range(1, cnt1_max+1):
 arr_size[i-1] = (i*(i+1), i)
# print(arr_size)
t = int(input())
for _t in range(t):
 s = input().strip()
 n = len(s)
 tot1 = [0]*(n+1)
 # print(tot1)
 for i in range(1, n+1):
  if s[i-1] == '1':
   tot1[i] = tot1[i-1] + 1
  else:
   tot1[i] = tot1[i-1]
 # print(tot1)        

 beauty = 0
 for size, cnt in arr_size:
  i = 0
  limit = n - size
  # print(size,cnt,limit)
  while i < limit+1:
   # print("tot1[i+size] " ,tot1[i+size],"  ", tot1[i])
   cnt1 = tot1[i+size] - tot1[i]
   # print("cnt ",cnt1)
   if cnt1 == cnt:
    beauty += 1
    i += 1
   else:
    i += abs(cnt1-cnt)
   # print("i :",i)
 print(beauty)
   


cnt1_max = 315
arr_size = [None]*cnt1_max
for i in range(1, cnt1_max+1):
 arr_size[i-1] = (i*(i+1), i)

t = int(input())
for _t in range(t):
 s = input().strip()
 n = len(s)
 tot1 = [0]*(n+1)
 for i in range(1, n+1):
  if s[i-1] == '1':
   tot1[i] = tot1[i-1] + 1
  else:
   tot1[i] = tot1[i-1]

 beauty = 0
 for size, cnt in arr_size:
  i = 0
  limit = n - size
  while i < limit+1:
   cnt1 = tot1[i+size] - tot1[i]
   if cnt1 == cnt:
    beauty += 1
    i += 1
   else:
    i += abs(cnt1-cnt)
 print(beauty)

cnt1_max = 315
arr_size = [None]*cnt1_max
for i in range(1, cnt1_max+1):
 arr_size[i-1] = (i*(i+1), i)

t = int(input())
for _t in range(t):
 s = input().strip()
 n = len(s)
 tot1 = [0]*(n+1)
 for i in range(1, n+1):
  if s[i-1] == '1':
   tot1[i] = tot1[i-1] + 1
  else:
   tot1[i] = tot1[i-1]

 beauty = 0
 for size, cnt in arr_size:
  i = 0
  limit = n - size
  while i < limit+1:
   cnt1 = tot1[i+size] - tot1[i]
   if cnt1 == cnt:
    beauty += 1
    i += 1
   else:
    i += abs(cnt1-cnt)
 print(beauty)

# cook your dish here
for i in range (int(input())):
 s = input()
 one = [0]*(len(s)+1)
 for i in range(len(s)):
  if s[i]=='1':
   one[i+1]=one[i]+1
  else:
   one[i+1]=one[i]
 ans = 0
 i=1
 r=2
 while r<=len(s):
  r=i+i**2
  j=0
  while j<=len(s)-r:
   if one[j+r]-one[j]==i:
    ans+=1
    j+=1 
   else:
    j+=abs(i-(one[j+r]-one[j]))
  i+=1
 print(ans)