Given a binary string S. The task is to count the number of substrings that starts and end with 1.
Note: The starting and the ending 1s should be different.
Example 1:
Input:
S = "10101"
Output: 3
Explanation: The 3 substrings are "101",
"10101" and "101".
Ã¢â¬â¹Example 2:
Input: 
S = "100"
Output: 0
Explanation: No substring that starts and
ends with 1.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countSubstr() which takes the string S as input and returns the count of the substrings that start and end with 1.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1 <= |S| <= 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3
class Solution:
	def countSubstr(self, S):
		# your code here

Solutions:
class Solution:

	def countSubstr(self, s):
		sum = 0
		count = 0
		for i in s:
			if i == '1':
				sum += count
				count += 1
		return sum


class Solution:

	def countSubstr(self, s):
		c = 0
		ans = 0
		for i in s:
			if i == '1':
				ans += c
				c += 1
		return ans


class Solution:

	def countSubstr(self, s):
		if len(set(s)) == 1 and s[0] == '0' or len(s) == 1:
			return 0
		if len(set(s)) == 1 and s[0] == '1':
			return len(s) * (len(s) - 1) // 2
		l = []
		for i in range(len(s)):
			if s[i] == '1':
				l.append(i)
		return len(l) * (len(l) - 1) // 2


class Solution:

	def countSubstr(self, S):
		times = 0
		for let in S:
			if let == '1':
				times += 1
		times -= 1
		return times * (times + 1) // 2


class Solution:

	def countSubstr(self, S):
		sum = 0
		j = S.count('1')
		k = j - 1
		while k > 0:
			sum += k
			k -= 1
		return sum


class Solution:

	def countSubstr(self, S):
		k = S.count('1')
		return k * (k - 1) // 2


class Solution:

	def countSubstr(self, S):
		count = 0
		for i in range(len(S)):
			if S[i] == '1':
				count += 1
		return count * (count - 1) // 2


class Solution:

	def countSubstr(self, S):
		count = s.count('1')
		return count * (count - 1) // 2


class Solution:

	def countSubstr(self, S):
		count = 0
		for i in S:
			if i == '1':
				count += 1
		if count <= 1:
			return 0
		elif count == 2:
			return 1
		else:
			realAnswer = 1
			j = 2
			x = count - 2
			for i in range(x):
				realAnswer += j
				j += 1
			return realAnswer


class Solution:

	def countSubstr(self, S):
		m = 0
		for i in S:
			if i == '1':
				m = m + 1
		return m * (m - 1) // 2


import re

class Solution:

	def countSubstr(self, S):
		final_count = 0
		str_start = 0
		for i in range(len(S)):
			char = S[i]
			if char == '1':
				str_start = str_start + 1
		if str_start <= 1:
			return 0
		else:
			return int(str_start * (str_start - 1) / 2)


class Solution:

	def countSubstr(self, S):
		ans = 0
		one = S.count('1')
		k = one - 1
		while k > 0:
			ans += k
			k -= 1
		return ans


from collections import Counter

class Solution:

	def countSubstr(self, S):
		c = Counter(S)
		return c['1'] * (c['1'] - 1) // 2


class Solution:

	def countSubstr(self, S):
		count = S.count('1')
		res = 0
		for i in range(count):
			res += i
		return res


class Solution:

	def countSubstr(self, s):
		n = s.count('1')
		if n == 1:
			return 0
		n = n - 1
		sumn = n * (n + 1) / 2
		return int(sumn)


class Solution:

	def countSubstr(self, s):

		def combi(n, r):
			if n - r < r:
				r = n - r
			mul = 1
			for i in range(r):
				mul = mul * (n - i)
				mul = mul // (i + 1)
			return mul
		one = 0
		for i in s:
			if i == '1':
				one += 1
		if one <= 1:
			return 0
		else:
			return combi(one, 2)


class Solution:

	def countSubstr(self, S):
		if S.count('1') == 1:
			return 0
		c = 0
		j = S.count('1')
		k = j - 1
		while k > 0:
			c += k
			k -= 1
		return c


class Solution:

	def countSubstr(self, S):
		if S.count('1') < 2:
			return 0
		summ = 0
		j = S.count('1')
		k = j - 1
		while k > 0:
			summ += k
			k -= 1
		return summ


class Solution:

	def fac(self, n):
		if n == 1:
			return 1
		if n == 0:
			return 1
		else:
			return n * self.fac(n - 1)

	def countSubstr(self, S):
		(c, k) = (0, 0)
		for i in S:
			if i == '1':
				c += 1
		return c * (c - 1) // 2


class Solution:

	def countSubstr(self, S):
		count = sum(list(map(int, S)))
		count_substr = 0
		if count > 1:
			count_substr = 1
			for i in range(2, count):
				count_substr += i
		return count_substr


class Solution:

	def countSubstr(self, S):
		m = 0
		n = len(S)
		for i in range(0, n):
			if S[i] == '1':
				m = m + 1
		return m * (m - 1) // 2


class Solution:

	def countSubstr(self, S):
		sum = 0
		x = S.count('1')
		y = x - 1
		while y > 0:
			sum += y
			y -= 1
		return sum


class Solution:

	def countSubstr(self, s):
		summ = 0
		x = s.count('1')
		k = x - 1
		while k > 0:
			summ += k
			k -= 1
		return summ


class Solution:

	def countSubstr(self, S):
		count = 0
		for i in S:
			if i == '1':
				count = count + 1
		return int(count * (count - 1) / 2)


import sys
sys.setrecursionlimit(2500)

class Solution:

	def countSubstr(self, arr):
		summ = 0
		j = arr.count('1')
		k = j - 1
		while k > 0:
			summ += k
			k -= 1
		return summ


import sys
sys.setrecursionlimit(12500)

class Solution:

	def countSubstr(self, arr):
		if len(arr) == 1:
			return 0
		else:

			def funn1(N, summ):
				if N == 0:
					return summ
				return funn1(N - 1, summ + N)
			j = arr.count('1')
			k = j - 1
			return funn1(k, 0)


class Solution:

	def nCr(self, n, r):
		return self.fact(n) / (self.fact(r) * self.fact(n - r))

	def fact(self, n):
		if n == 0:
			return 1
		res = 1
		for i in range(2, n + 1):
			res = res * i
		return res

	def countSubstr(self, S):
		count = 0
		for i in S:
			if i == '1':
				count += 1
		if count < 2:
			return 0
		return int(self.nCr(count, 2))


class Solution:

	def countSubstr(self, S):
		c = S.count('1')
		return c * (c - 1) // 2


class Solution:

	def countSubstr(self, S):
		m = S.count('1')
		return m * (m - 1) // 2


class Solution:

	def countSubstr(self, S):
		c = s.count('1')
		return int(c * (c - 1) / 2)


import math as m

class Solution:

	def nCr(self, n, r):
		mul = k = 1
		for i in range(1, n + 1):
			mul = mul * i
			if i == n - 2:
				k = mul
		return mul // (2 * k)

	def countSubstr(self, S):
		n = S.count('1')
		return self.nCr(n, 2)


class Solution:

	def countSubstr(self, S):
		s = S
		d = dict()
		ans = 0
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = 0
			else:
				d[s[i]] += 1
				if s[i] == '1':
					ans += d[s[i]]
		return ans


class Solution:

	def countSubstr(self, S):
		ct = 0
		for it in S:
			if it == '1':
				ct += 1
		return ct * (ct - 1) // 2


class Solution:

	def countSubstr(self, S):
		c = S.count('1')
		if c <= 1:
			return 0
		else:
			return c * (c - 1) // 2


class Solution:

	def countSubstr(self, S):
		c = 0
		for i in range(len(s)):
			if s[i] == '1':
				c = c + 1
		return int(c * (c - 1) / 2)


class Solution:

	def countSubstr(self, S):
		a = S.count('1')
		return a * (a - 1) // 2


class Solution:

	def countSubstr(self, S):
		res = S.count('1')
		return res * (res - 1) // 2


class Solution:

	def countSubstr(self, S):
		c = 0
		for i in range(len(S)):
			if S[i] == '1':
				c += 1
			else:
				continue
		return c * (c - 1) // 2


class Solution:

	def countSubstr(self, S):
		x = S.count('1')
		return x * (x - 1) // 2
if __name__ == '__main__':
	t = int(input())
	for tc in range(t):
		s = input()
		ob = Solution()
		print(ob.countSubstr(s))


class Solution:

	def countSubstr(self, S):
		c = 0
		for i in S:
			if i == '1':
				c += 1
		if c < 2:
			return 0
		else:
			return int(c * (c - 1) / 2)
if __name__ == '__main__':
	t = int(input())
	for tc in range(t):
		s = input()
		ob = Solution()
		print(ob.countSubstr(s))


class Solution:

	def countSubstr(self, S):
		if '1' not in S:
			return 0
		sum = 0
		for i in range(len(S)):
			if S[i] == '1':
				first1 = i
				break
		j = first1 + 1
		sum = 0
		inc = 1
		while j < len(S):
			if S[j] == '1':
				sum = sum + inc
				inc = inc + 1
			j += 1
		return sum
if __name__ == '__main__':
	t = int(input())
	for tc in range(t):
		s = input()
		ob = Solution()
		print(ob.countSubstr(s))


class Solution:

	def countSubstr(self, S):
		c = 0
		for ch in S:
			if ch == '1':
				c += 1
		return int(c * (c - 1) / 2)


class Solution:

	def countSubstr(self, S):
		n = []
		for i in range(len(S)):
			if S[i] == '1':
				n.append(i)
		return int(len(n) * (len(n) - 1) / 2)


from math import factorial as F

class Solution:

	def countSubstr(self, S):
		t = S.count('1')
		return F(t) // (F(t - 2) * 2) if t > 1 else 0


class Solution:

	def countSubstr(self, S):
		cou = S.count('1')
		if cou == 1:
			return 0
		return cou * (cou - 1) // 2


class Solution:

	def countSubstr(self, S):
		n = S.count('1')
		return n * (n - 1) // 2


class Solution:

	def countSubstr(self, S):
		ones = 0
		for ch in S:
			if ch == '1':
				ones += 1
		return ones * (ones - 1) // 2


class Solution:

	def countSubstr(self, s):
		c = s.count('1')
		ans = c * (c - 1) // 2
		return ans
		n = len(s)
		c = 0
		for i in range(0, n):
			for j in range(i + 1, n + 1):
				sub = s[i:j]
				if len(sub) > 1:
					if sub[0] == '1' and sub[-1] == '1':
						c += 1
		return c


class Solution:

	def countSubstr(self, S):
		ans = 0
		inc = 0
		for i in range(len(S)):
			if S[i] == '1':
				ans = ans + inc
				inc += 1
		return ans


class Solution:

	def countSubstr(self, s):
		c = s.count('1')
		return c * (c - 1) // 2