Anagrams

Time limit1sMemory limit128 MB

Summary

Given several word lists, print the first word in each list that has the most anagrams, along with that count.

Level: Easy3 of 10
Topics: Hash map, String, Sorting
Solved: No attempts yet

Problem

Two words are anagrams if they contain the same letters but in a different order. For example, ant and tan are anagrams, but ant and ton are not.

You are given several lists of words. For each list, find the word that has the most anagrams within that list, and report how many anagrams it has.

Input

The input consists of several lists. Each list begins with a line containing an integer $n$ ( $0 < n \le 1000$ ), the number of words in the list. The next $n$ lines each contain one word. A final line containing the single number $0$ marks the end of the input and must not be processed.

Every word consists of lowercase letters only and has at most $8$ letters. Every list is guaranteed to contain at least one word that has an anagram somewhere in the same list.

Output

For each list, output one line: the word that has the most anagrams within the list, then a space, then the number of anagrams it has.

The word you print must be the first occurrence in the list among the words that share its letters. If more than one word ties for the highest number of anagrams, print only the one that comes first in the list.

Examples2

Example 1

Input

6
not
ant
tan
ton
cat
nat
4
time
timer
emit
mote
0

Expected output

ant 2
time 1

Example 2
Input
```
4
abc
cba
xyz
zyx
0
```
Expected output
```
abc 1
```