Koło Młodych Miłośników Łamania Szyfrów pracuje nad odszyfrowaniem pewnego starożytnego manuskryptu. Jądrem systemu ma być samouczący się analizator tekstu, a jego pierwszym modułem ma być "zliczacz liter", którego opracowanie powierzono Tobie.

Opracuj program ZLI, który:
- wczyta ze standardowego wejścia tekst do analizy,
- dla każdej litery obliczy liczbę jej wystąpień w tekście,
- wypisze wynik na standardowe wyjście.

Input

W pierwszym wierszu N - liczba wierszy tekstu do analizy (N≤150). W każdym z następujących N wierszy ciąg złożony z maksymalnie 200 znaków spośród małych i wielkich liter alfabetu łacińskiego ('a'..'z', 'A'..'Z') oraz spacji.

Output

W kolejnych wierszach litery od 'a' do 'z' i od 'A' do 'Z' w tej kolejności, a po każdej literze spacja i liczba wskazująca, ile razy ta litera wystąpiła w tekście.

Uwaga: pomiń litery, które nie występują w tekście.

Example

Input:
2
ala ma kota
Ola ma psa

Output:
a 7
k 1
l 2
m 2
o 1
p 1
s 1
t 1
O 1

Zadanie pochodzi z Olimpiady dla Gimnazjum z roku szkolnego 2006/2007 z I etapu.