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 $T$
is called Tokushuna if
$|T| ≥ 3$
)$\texttt{1}$
(one)$|T|-2$
) number of $\texttt{0}$
(zero)Here $|T|$
is the length of string $T$
.
For example, $\texttt{10001}$
, $\texttt{101}$
, and $\texttt{10001}$
is Tokushuna string. But, $\texttt{1100}$
, $\texttt{1111}$
, and $\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 $S$
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 .
In the first line of the input there is an integer $T$
, the number of test cases. In each test case, you are given a binary string $S$
consisting of only $\texttt{0}$
and $\texttt{1}$
.
Subtask 1 (50 Points)
$1 ≤ T ≤ 100$
, $1 ≤ |S| ≤ 100$
Subtask 2 (50 points)
$1 ≤ T ≤ 100$
, $1 ≤ |S| ≤ 10<sup>5$
For each test case output a line $\texttt{Case X: Y}$
where $X$
is the case number and $Y$
is the number of Tokushuna string can be found from all possible the substring of string $S$
.
Input | Output |
---|---|
3 10001 10101 1001001001 | Case 1: 1 Case 2: 2 Case 3: 3 |
In the first case |