LEXISORT - Easy Sorting

Given is a list of words and a lexicographical ordering according to the ascii alphabet. Your task is to sort the words in increasing order.

Input

The first line contains the numbers of test cases k (k< 100). Every test case consists of n+1 (1 < n < 50000) lines. Each line contains of a string of 10 characters. The first line of each test case contains n.

Output

Output the sorted list of words.

Example

Input:
2
2
helloworld
worldhello
2
aaaaaaaaaa
Aaaaaaaaaa

Output:
helloworld
worldhello
Aaaaaaaaaa
aaaaaaaaaa

Added by:Simon
Date:2005-04-13
Time limit:1s
Source limit:8083B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET

hide comments
2012-08-16 17:28:49 Arkadiusz Bulski
O(n) time complexity is probably necessary, so radix sort and by extension count sort.
2012-05-05 05:12:38 ria yunita sari
what sorting is used for this problem? (time limit exceeded)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.