Kick Start

Ksenia loves reading, so she starts each day by reading a fragment from her favorite book before beginning the rest of her morning routine. A fragment is simply a substring of the text. Ksenia is a bit superstitious and believes her day will be lucky if the fragment she reads starts with the string KICK, then continues with 0 or more characters, and eventually ends with the string START, even if the fragment as a whole makes little sense.

Given the text of the book, count the number of different lucky fragments Ksenia can read before the book gets old and she needs to buy another one. Two fragments are considered different if they start or end at different positions in the text, even if they read the same. Also note that different lucky fragments may overlap.

The first line of the input gives the number of test cases, T. T lines follow, each containing a single string S consisting of upper case English letters only.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of different lucky fragments in the text of this test case.

• 1 ≤ T ≤ 100.
• S consists of upper case English letters only.

There are three lucky fragments in the first test case: KICKSTARTPROBLEMNAMEDKICKSTART and two occurrences of KICKSTART. The text in the second test case has no lucky fragments at all.