Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Nobita and Shizuka

By iammarajul · Limits 1s, 512 MB

Probably, You all Know About The Famous Japanese Cartoon Character Nobita and Shizuka. Nobita Shizuka are very Good friend. However , Shizuka Love a special kind of string Called Tokushuna.

A string TT is called Tokushuna if

  • The length of the string is greater or equal than 3 (T3|T| ≥ 3)
  • It starts and ends with a charecter 1\texttt{1} (one)
  • It contains (T2|T|-2) number of 0\texttt{0} (zero)

Here T|T| is the length of string TT.

For example, 10001\texttt{10001}, 101\texttt{101}, and 10001\texttt{10001} is Tokushuna string. But, 1100\texttt{1100}, 1111\texttt{1111}, and 0000\texttt{0000} are not.

One day Shizuka gave a problem to Nobita and promised to go on a date with him if he was able to solve the problem. Shizuka gave a string SS and asked him to count the number of Tokushuna strings that can be found from all possible substrings of string S. Nobita wants to go on a date with Shizuka but you know he is very weak in maths and counting. And in this time Doraemon is not present to help him. So he needs your help to solve the problem .

Input

In the first line of the input there is an integer TT, the number of test cases. In each test case, you are given a binary string SS consisting of only 0\texttt{0} and 1\texttt{1}.

Subtask 1 (50 Points)

1T1001 ≤ T ≤ 100, 1S1001 ≤ |S| ≤ 100

Subtask 2 (50 points)

1T1001 ≤ T ≤ 100, 1S10<sup>51 ≤ |S| ≤ 10<sup>5

Output

For each test case output a line Case X: Y\texttt{Case X: Y} where XX is the case number and YY is the number of Tokushuna string can be found from all possible the substring of string SS.

Sample

InputOutput
3
10001
10101
1001001001
Case 1: 1
Case 2: 2
Case 3: 3

In the first case 10001\texttt{10001} is itself is a Tokushuna string. In the second case there are 2 substrings (S[1:3] 101 and S[3:6]) that are 101\texttt{101} that are Tokushuna string.


Discussion

Statistics


80% Solution Ratio

prodip_bsmrstuEarliest, Aug '20

iammarajulFastest, 0.0s

Aimon026Lightest, 0 B

aNkanpy.pritomShortest, 99B

Submit

Login to submit

Editorial

Subtask 1: Generate all possible substrings and count the number of Tokushuna substrings. The comple...

Toph uses cookies. By continuing you agree to our Cookie Policy.