from typing import List
import sys

def compress(s: str) -> str:
    n = len(s)
    dp = [float('inf')] * (n + 1)
    backtrack = [(-1, "")] * (n + 1)
    dp[0] = 0  # empty string

    for i in range(1, n + 1):
        # try all possible block sizes that end at i
        for l in range(1, i + 1):
            substr = s[i - l:i]
            max_repeat = 1
            # check how many times substr repeats ending at position i
            while i - l * max_repeat >= 0 and s[i - l * max_repeat:i - l * (max_repeat - 1)] == substr:
                max_repeat += 1
            max_repeat -= 1
            if max_repeat == 0:
                continue
            start_pos = i - l * max_repeat
            cost = dp[start_pos] + len(substr) + len(str(max_repeat))
            if cost < dp[i]:
                dp[i] = cost
                backtrack[i] = (start_pos, substr + str(max_repeat))

    # Reconstruct compressed string
    result = []
    i = n
    while i > 0:
        prev, part = backtrack[i]
        result.append(part)
        i = prev

    return ''.join(reversed(result))

def solve_all(strings: List[str]) -> List[str]:
    return [compress(s) for s in strings]  # process each string independently

if __name__ == "__main__":
    import sys
    input_lines = [line.strip() for line in sys.stdin if line.strip()]
    T = int(input_lines[0])
    strings = input_lines[1:T+1]
    results = solve_all(strings)
    for res in results:
        print(res)