Problem C
Kanglish : Analysis on Artificial Language

The late Prof. Kanazawa made an artificial language named Kanglish, which is similar to English, for studying mythology. Words and sentences of Kanglish are written with its own special characters called "Kan-characters". The size of the set of the Kan-characters is 38, i.e., there are 38 different Kan-characters in the set. Since Kan-characters cannot be directly stored in a computer because of the lack of a coded character set, Prof. Kanazawa devised a way to represent each Kan-character as an alphabetical letter or an ordered combination of two alphabetical letters. Thus, each Kan-character is represented as one of the following 26 letters

"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", and "z",

"ld", "mb", "mp", "nc", "nd", "ng", "nt", "nw", "ps", "qu", "cw", and "ts".

The representations of words in Kanglish are separated by spaces. Each sentence is written in one line, so there are no periods or full stops in Kanglish. All alphabetical letters are in lower case, i.e., there are no capitalizations.

We currently have many documents written in Kanglish with the alphabetical representation. However, we have lost most of Prof. Kanazawa's work on how they can be translated. To recognize his work, we have decided to first analyze them statistically. The first analysis is to check sequences of consecutive Kan-characters in words.

For example, a substring "ic" in a word "quice" indicates an ordered pair of two adjacent Kan-characters that are represented by "i" and "c". For simplicity, we make a rule that, in the alphabetical representation of a word, a Kan-character is recognized as the longest possible alphabetical representation from left to right. Thus, a substring "ncw" should be considered as a pair of "nc" and "w". It does not consist of "n" and "cw", nor "n", "c", and "w".

For each Kan-character, there are 38 possible pairs of that Kan-character and another Kan-character, e.g. "aa", "ab", ..., "az", "ald", ..., "ats". Thus, mathematically, there is a total of 1444 (i.e., 38x38) possible pairs, including pairs such as "n" and "cw", which is actually not allowed according to the above rule.

Your job is to write a program that counts how many times each pair occurs in input data. For example, in the sentence

	qua ist qda quang quice

For simplicity, a newline at the end of a line is considered as a space. Thus in the above example, "e" is followed by a space.

Input

n
line1
line2
...
linen

The first line of the input is an integer n, which indicates the number of lines that follow. Each line except for the first line represents one Kanglish sentence. You may assume that n <= 1000 and that each line has at most 59 alphabetical letters including spaces.

Output

a kc1 m1
b kc2 m2
c kc3 m3
...
ts kc38 m38

The output consists of 38 lines for the whole input lines. Each line of the output has two strings and an integer. In the i-th line in the output, the first string is the alphabetical representation of the i-th Kan-character in the Kan-order. For example, the first string of the first line is "a", that of the third line is "c", and that of the 37th line is "cw". The first string is followed by a space.

The second string in the i-th line (denoted by kc_i above) shows the alphabetical representation of a Kan-character that most often occurred directly after the first Kan-character. If there are two or more such Kan-characters, the first one in the Kan-order should be printed. The second string is followed by a space.

The integer (denoted by m_i above) in the i-th line shows the number of times that the second Kan-character occurred directly after the first Kan-character. In other words, the integer shows the number of times that ``the ordered pair of the first Kan-character and the second Kan-character'' appeared in the input. The integer is followed by a newline.

Suppose the 28th output line is as follows:

mb e 4

Note that if the i-th Kan-character does not appear in the input, or if the i-th Kan-character is not followed by any other Kan-characters but spaces, the second string in the i-th output line should be "a" and the third item should be zero.

Although the output does not include spaces, Kan-characters that appear with a space in-between is not considered as a pair. Thus, in the following example

abc def

Sample Input

3
nai tiruvantel ar varyuvantel i valar tielyama nu vilya
qua ist qda quang ncw psts
svampti tsuldya jay quadal ciszeriol

Output for the Sample Input

a r 3
b a 0
c i 1
d a 2
e l 3
f a 0
g a 0
h a 0
i s 2
j a 1
k a 0
l y 2
m a 1
n a 1
o l 1
p a 0
q d 1
r i 1
s t 1
t i 3
u v 2
v a 5
w a 0
x a 0
y a 3
z e 1
ld y 1
mb a 0
mp t 1
nc w 1
nd a 0
ng a 0
nt e 2
nw a 0
ps ts 1
qu a 3
cw a 0
ts u 1

First Input Data

Test your program against this first input data.