ALPHABETS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
VOWELS = set('AEIOU')

def cost(a, b):
    if a == b:
        return 0
    if (a in VOWELS) ^ (b in VOWELS):
        return 1
    return 2

def min_cost(text):
    return min(sum(cost(a, b) for b in text) for a in ALPHABETS)

for case in range(int(input())):
    text = input().strip()
    print(f'Case #{case+1}: {min_cost(text)}')

from collections import defaultdict

def transpose(grid):
    return [list(row) for row in zip(*grid)]

def xwin(grid):
    feasible = defaultdict(set)
    for i, row in enumerate(grid):
        if 'O' in row:
            continue
        moves = frozenset((i,j) for j, v in enumerate(row) if v == '.')
        feasible[len(moves)] |= {moves}
    for j, col in enumerate(transpose(grid)):
        if 'O' in col:
            continue
        moves = frozenset((i,j) for i, v in enumerate(col) if v == '.')
        feasible[len(moves)] |= {moves}
    return feasible

for case in range(int(input())):
    grid = [list(input().strip()) for _ in range(int(input()))]
    feasible = xwin(grid)
    if not feasible:
        answer = 'Impossible'
    else:
        minimum = min(feasible)
        different = len(feasible[minimum])
        answer = f'{minimum} {different}'
    print(f'Case #{case+1}: {answer}')