Dominosa

With $n$ different symbols there are $n(n+1)/2$ unordered pairs of symbols, counting a pair of two equal symbols as one of them. One domino per pair makes a full set, and a full set covers exactly $n(n+1)$ squares, so it fits an $n$ by $n+1$ rectangle with no gaps and no overlaps.

Lay a full set out that way, erase the edges of the dominoes, and keep only the symbol written in each square. What is left is a puzzle. On the left of the picture below is an original layout of the 28 dominoes made from the seven numbers 0 to 6, and on the right is the same layout with the edges erased.

Read the puzzle and recover the original layout. The layout always exists and it is unique.

The input holds several puzzles.

The first line of a puzzle has an integer $n$ ($2 \le n \le 12$). The next $n$ lines each hold $n+1$ characters separated by single spaces. The characters come from the first $n$ lowercase letters, a through the $n$th letter of the alphabet.

The $n \times (n+1)$ grid was built by placing each of the $n(n+1)/2$ unordered pairs exactly once, and only one placement matches the grid.

A line holding a single 0 ends the input.

For each puzzle print the recovered layout in the same format as the input, except that the two characters of a horizontal domino are joined by an equals sign (=) instead of a space. Every other gap stays a single space.

Print one blank line between consecutive grids, and no blank line after the last grid.