Original problem statement (in Polish) can be found here.

Pantaleon the Visual Artist wants to open his own modern art exhibition. Abstract paintings are the most important elements of every such event. Pantaleon already has the general vision of his masterpiece, its actual realization is the main problem.

In order to emphasize beauty of the world, lying in its apparent simplicity, painting won't be very complicated. Colourful grid of square-shaped fields will be just fine, perfectly in the spirit of impressionist minimalism.

Pantaleon considers the message as the most important part of performing art. To be absolutely sure that potential spectators will see the message, Pantaleon wants to place specific artistic themes in his painting. Themes also can be represented as a colourful grid of squares. Moreover, they are universal enough that they can be recognized even when rotated by 90 degrees multiple times.

Help Pantaleon to paint a picture that will contain all artistic themes he chose. Painting should consist of as few squares as possible - our artist takes minimalism really seriously (also, renting a room with big walls can cost fortune).

Input

The first line contains a single integer t (t <= 10), denoting the number of testcases. Then, descriptions of the testcases follow.

First line of the description consists of a single integer k (1 <= k <= 20) - number of artistic themes to include in the painting. Then, descriptions of the themes follow.

Description of a theme starts with two integers n_i, m_i (1 <= n_i, m_i <= 20) - number of rows and columns in the grid representing a theme, respectively. In the next n_i lines descriptions of rows follow. Every row is described by a string of length m_i, containing only lowercase characters of English alphabet. Letters denote the colours in subsequent columns, from left to right. Same letters correspond to the same colours, different letters mean different colours.

Output

For every testcase you should find a painting that contains all artistic themes chosen by Pantaleon. Painting contains a given theme if you can cut out a grid from the painting (in one piece) that represents that theme (it can be rotated by 90 degrees any number of times).

Description of a painting starts with two integers p and q - number of rows and columns in the final painting (1 <= p*q <= X_i*X_i*k). X_i denotes the maximum value among all n_i and m_i in a testcase.

Then p lines should follow, every line containing a string of length q containing only lowercase English characters - the description of the painting.

Example

Input:

1
3
2 2
ab
cd
2 1
d
c
1 3
cca

Output:

2 3
bdd
acc

Explanation

First theme is placed in the picture after rotating it 90 degrees to the left. Second theme appears directly, twice. Third theme can be found rotated by 90 degrees twice (upside-down).

Scoring

If the painting is correct, it is worth p*q/(X_i*X_i*k) points. Overall score is equal to sum of individual scores. Score for the sample output is equal to 2*3/(3*3*3), about 0.22.