Google Kick Start 2021 Round E - A(Shuffled Anagrams)

T = int(input())

for tc in range(1, T+1):
    S = input()
    arr = [[] for _ in range(26)]
    count = [0] * 26
    
    for i in range(len(S)):
        arr[ord(S[i])-97].append(i)
        count[ord(S[i])-97] += 1

    check = False
    max_value = 0
    max_index = 0
    for i in range(26):
        if count[i] > len(S)-count[i]:
            print('Case #{}: IMPOSSIBLE'.format(tc))
            check = True
            break
        if count[i] > max_value:
            max_value = count[i]
            max_index = i
    
    if check:
        continue
    
    new_arr = [[] for _ in range(26)]
    cur = (max_index+1)%26
    for i in range(26):
        temp = (i+max_index)%26
        if cur == temp:
            cur = (cur+1)%26
        while count[temp] > 0:
            if len(arr[cur]) == 0:
                cur = (cur+1)%26
                continue
            
            new_arr[temp].append(arr[cur][0])
            arr[cur].pop(0)
            count[temp] -= 1
    
    new_S = ['a'] * len(S)
    for i in range(26):
        for j in range(len(new_arr[i])):
            new_S[new_arr[i][j]] = chr(i+97)
    
    result = ''
    for i in range(len(new_S)):
        result += new_S[i]
    print('Case #{}: {}'.format(tc, result))