Taco's Flower Shop

In Taco's Flower Shop challenge, you are given several shops, each described by a string in which every character denotes a type of flower. Your task is to choose the flower that appears most frequently in each shop's string. In case there is a tie (i.e. two or more flower types appear the same maximum number of times), choose the one that comes first in lexicographical order (i.e. alphabetical order).

Mathematically, if for a string S and for each character c, f(c) denotes its frequency, then you must choose a flower c such that for any other flower d, either [ f(c) > f(d) \quad \text{or} \quad \bigl(f(c) = f(d) \text{ and } c < d\bigr). ] Process multiple test cases from standard input and output the result for each on a separate line.

inputFormat

The input is given via standard input (stdin). The first line contains an integer T representing the number of test cases. For each test case, the first line contains an integer N, the number of shops. The following N lines each contain a non-empty string where each character (from 'a' to 'z') represents a type of flower.

outputFormat

For each test case, output one line to standard output (stdout) with N space‐separated characters. Each character is the answer for the corresponding shop: the most frequent flower in that shop’s string (with ties broken by choosing the alphabetically first flower).## sample

2
3
abacc
ccbbdd
eeffee
2
aaa
bbb

a b e
a b