Trong một lớp học, giáo viên ghi lại các từ mà học sinh phát biểu trong giờ học. Một từ có thể xuất hiện nhiều lần.

Hãy đếm số lần xuất hiện của mỗi từ theo thứ tự từ điển tăng dần.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 1000) là số từ được ghi lại.

N dòng tiếp theo, mỗi dòng chứa một từ chỉ gồm các chữ cái tiếng Anh không dấu.

Dữ liệu ra

In ra mỗi từ khác nhau cùng số lần xuất hiện của nó theo định dạng:

tu so_lan_xuat_hien

Các từ được in theo thứ tự từ điển tăng dần.

Ví dụ

Input

8
apple
banana
apple
orange
banana
apple
grape
orange

Output

apple 3
banana 2
grape 1
orange 2