You are given a list of characters in English alphabets (ASCII ≥ 97). Sort the characters and give the number of occurrences of every character.

Input

The first line contains an integer n, the number of characters, followed by n lines with a character in every line.

Output

Print the characters in sorted order with no duplicates.

Output format: “character number_of_occurrences”

Constraints

1 ≤ n ≤ 100

Example

Input:
5
a
f
b
a
f

Output:
a 2
b 1
f 2