Typesetting

Modern fonts generally come in two varieties: outline fonts, whose glyphs (the individual character shapes) are defined mathematically as a set of curves, and bitmap fonts, whose glyphs are defined as patterns of pixels. Fonts may also carry embedded information such as kerning pairs (adjusting the spacing between certain pairs of glyphs, such as "AW", so that they appear correctly spaced), tracking hints (managing inter-glyph spacing), antialiasing hints (smoothing pixelated edges), and much more. Modern fonts are more than a simple collection of shapes, and displaying them properly is a common programming challenge.

For this problem we concern ourselves with bitmapped fonts and a simple form of typesetting called glyph packing. The idea is to pack the glyphs as tightly as possible while keeping at least one horizontal pixel of separation between glyphs. For example, the glyphs for the Roman characters "P" and "J" can be pushed together until they are as close as possible without touching horizontally.

After packing, pixels from distinct glyphs may be adjacent diagonally or vertically, but never horizontally. Two pixels from different glyphs may sit directly above and below each other, and they may touch on a diagonal, but they may never occupy horizontally adjacent cells.

Glyph packing has a useful property: it is easy to build "fancy" glyphs into a font so that the same simple packing process creates special effects with no extra work.

Glyph packing does have caveats. Consider a glyph for a hyphen followed by a glyph for an underscore. Under the one-horizontal-pixel-of-separation rule alone they could slide arbitrarily close, because their visible pixels never share a row. Something more is needed, and that something is hinting inside the glyphs themselves. For our purposes, hinting is limited to "invisible" pixels that count as a pixel for the purpose of packing, but are not drawn when the packed result is displayed. With invisible pixels filling out each glyph's shape, the hyphen and the underscore pack with the proper separation.

The formal definition of a proper packing is as follows:

1. Glyphs are packed as close together as possible without letting any pixels from different glyphs be immediately horizontally adjacent.
2. For any two glyphs, they may not be packed so that a pixel of the left glyph at a given height ends up positioned to the right of a pixel at the same height in the right glyph.

Condition 2 is easy to picture: imagine two glyphs sitting side by side with a small space between them. As you "squeeze" them together, condition 2 says that their pixels are not allowed to "pass through" one another.

The input is a sequence of test cases, each describing a set of glyphs to be packed. Within a test case all glyphs have the same height, and an integer N on the first line gives that height. The next N lines contain the glyphs. An empty pixel is written as a dot .. A non-empty pixel is written as a hash mark # for a visible pixel, or a zero 0 for an invisible pixel. Adjacent glyphs are separated by a single column of space characters.

A test case always contains more than one glyph, and at least one of the glyphs always contains at least one visible pixel. Every glyph has at least one non-empty pixel in both its leftmost and its rightmost column, and every glyph has at least one non-empty pixel at the same height as at least one other glyph in the same test case. A glyph's dimensions range from 1×1 up to 20×20, and a test case contains at most 20 glyphs. The input ends with a line containing 0 for N; that terminating case is not processed.

For each test case, first print the number of that test case (starting from 1) on a line by itself. Then print the proper packing of the glyphs, using the dot . character for both empty pixels and invisible pixels, and the hash mark # character for visible pixels. Omit any leading or trailing empty columns (columns that contain no visible pixel) so that both the leftmost and the rightmost printed column contain at least one visible pixel.