Count "010"
Problem
You will be given a string S consisting of only 0s and 1s.
You need to output number of 010 substrings in the given string S.
Read more about substrings here: Click here!
See Sample test-case for more understanding.
Input format:
First line consists of an integer Q, total queries that need to be answered.
Each of the next Q lines consist of a String S.
Output format:
For each query, output number of 010 substrings in the given string S.
Constraints:
1 <= Q <= 10
1 <= |S| <= 10^5
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
In the given string 0101, only one occurrence of "010" as a substring is there (index 1 to index 3).
So, output is 1.
