ADS25S1

Dada uma lista duplamente encadeada de caracteres, conte o número de vezes que cada elemento aparece na lista, gerando uma nova lista simplesmente encadeada ordenada tendo como informações o caracter e quantas vezes ele aparece na lista original.

Entrada

A primeira linha contém N, que representa o número de casos de teste entre 1 e 100

Em seguinda, tem-se N linhas, cada uma representando uma lista,  com uma sequencia de caracteres em maiúsculo (A..Z) de comprimento entre 1 e 10² caracteres.

Saída

Conjunto de linhas que representa a contagem realizada para lista dada, em que cada linha contém um caracter maiúsculo e o número de vezes que o mesmo aparece no input. As linhas de resultado de cada caso de teste estão em ordem alfabética. Os conjuntos de linhas de resultado de cada caso de teste são separados por uma linha em branco.

Exemplo

Entrada

2

ATTGCATG

TTTAGGGC

Saída

A 2

C 1

G 2

T 3

A 1

C 1

G 3

T 3