DCEPC906 - Picture Perfect

no tags 

Developers at DCE Coders love to work on challenging new problems. During one of their fun sessions, they were watching the movie “THE DARK KNIGHT RISES” but suddenly the picture quality started degrading and eventually the whole picture became distort. They waited for hours and hours for the quality to become good again but all that waiting was in vain.

The very next day during their programming session, they came up with a whole new idea of writing a program which when run with the TV connected to a laptop could get back the original picture.

The idea they used was:-

Imagine the whole T.V. screen to be made of small pixels. Now these pixels are so small that the pixels which are nearer to each other have almost the same properties. So if they can scan the whole screen and detect which pixels have the same property and then club them together, they can get back the original picture. Of course this task is more complicated that it appears here.

Now they want to recruit new members and want you to write a small piece of code for them which will form the backbone of their project.

Input

You are given a matrix with each cell containing a character (a..z). The characters are given in a very random manner. Your task is to club all the same characters together and also arrange them in such a manner that they form a proper increasing order.

The first line of input will contain an integer t representing the number of test cases. Each test case begins with a line containing two integers r and c representing the number of rows and columns respectively.

The next r lines contain c characters each.

1 ≤ t ≤ 1000

1 ≤ r ≤ 50

1 ≤ c ≤ 50 

Output

For each test case, output the correct matrix.

Example

Input:
1
4 3
bcd
aef
tyu
awe

Output:
aab
cde
eft
uwy

Note

All characters are LOWER CASE only. And don’t forget the increasing order of characters in the output matrix.



Added by:dce coders
Date:2012-08-26
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Own Problem