Genetic Search

Technology has greatly changed the field of biology in the last decade, since biological information can be digitized and analyzed by computer. One of the most basic analysis tasks is counting the number of occurrences (or near-occurrences) of a search string S inside of another string L that is at least as long as S.

For this problem, you are given pairs of strings S and L. Both strings contain only the uppercase characters A, G, C, and T. For each of the following types of search strings, count the number of times that type occurs as an exact substring of L:

• Type 1: S, without any changes.
• Type 2: All unique strings that can be made by deleting one character from S (for example, AGC can become AG, AC, or GC).
• Type 3: All unique strings that can be made by inserting one character in S (for example, AG can become any of the following: AAG, GAG, CAG, TAG, AGG, ACG, ATG, AGA, AGC, or AGT).

If two or more different modifications of S result in the same string, count only the occurrences of that string once.

The input file contains multiple test cases, each of which contains two strings: S followed by L. The length of S is at least 2 characters and at most the length of L. The length of L is at most 100 characters. The last test case is followed by a line containing a single zero.

For each test case, print the case number (beginning with 1) followed by the number of occurrences of Type 1, then Type 2, then Type 3.