tests = int(input())

for case in range(1, tests+1):
    choices = input()
    lengths = []
    prev_char = ""
    for char in choices:
        if char == prev_char:
            lengths[-1] += 1
        else:
            lengths.append(1)
        prev_char = char
    if choices[-1] == choices[0] and len(lengths) > 1:
        lengths[0] = lengths[0] + lengths[-1]
        lengths.pop()
    if len(lengths) == 1:
        changes = (len(choices) + 1) // 2
    else:
        changes = 0
        for length in lengths:
            if length > 1:
                changes += length // 2
    print(f"Case #{case}: {changes}")