SPOJ Brasil

A administração da Universidade planeja construir uma nova praça de alimentação para substituir os vários pequenos e inadequados refeitórios espalhados pelo campus. Para estimar o número de lugares necessários na nova praça de alimentação, foi realizado um experimento para medir o número máximo de clientes dentro dos refeitórios a qualquer instante. Eles contrataram vários estudantes como porteiros, e os posicionaram em cada entrada e saída de todos os refeitórios. A tarefa dos porteiros era anotar em pequenos cartões a hora que cada cliente entrou ou saiu do refeitório (uma carta para cada evento). Em cada carta, eles escreveram a hora, no formato HH:MM:SS, e o evento associado ('E' para entrada, 'X' para saída).

O experimento teve início na manhã, antes do café-da-manhã, e terminou à noite, após do jantar. Os porteiros tinham seus relógios sincronizados, e os refeitórios estavam vazios tanto antes quanto depois do experimento (ou seja, não havia nenhum cliente antes do café-da-manhã e nenhum cliente permaneceu depois do jantar). Os porteiros escreveram exatamente um cartão para cada cliente que entrou e para cada cliente que saiu.

Após o experimento, as cartas foram coletadas e enviadas à administração para serem processadas. A tarefa, no entanto, não foi tão fácil como planejada, pois dois problemas ocorreram. Primeiramente, os cartões foram amontoados de forma aleatória e portanto necessitavam ser ordenados; isso é bastante fácil mas demorado para ser feito à mão. Mas o pior é que, apesar dos cartões possuirem as horas corretas, alguns porteiros esqueceram de escrever a letra correspondente ao evento. A administração da Universidade decidiu que necessitava da ajuda de um expert!

Dado um conjunto de cartões com horas e eventos (o evento pode estar faltando), escreva um programa que determine o número máximo de clientes que poderiam ter estado dentro dos refeitórios a qualquer momento.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém um inteiro N indicando o número de cartões coletados no experimento (2 ≤ N ≤ 64800). Cada uma das próximas N linhas contém a informação escrita em um cartão, que consiste da especificação da hora, seguida por um espaço em branco, seguida pela especificação do evento. A especificação da hora é dada no formato HH:MM:SS, onde HH representa horas (06 ≤ HH ≤ 23), MM representa minutos (00 ≤ MM ≤ 59) e SS representa segundos (00 ≤ SS ≤ 59). Em cada caso de teste, nenhum par de cartas representa o mesmo instante de tempo. A especificação de evento é um único caractere: 'E' para entrada, 'X' para saída e '?' para incerto. Informações podem estar faltando, mas as informações dadas sempre estão corretas (ou seja, o instante de tempo anotado no cartão é válido). Além disso, se um cartão descreve uma entrada, então um cliente realmente entrou no refeitório naquele momento; se um cartão descreve uma saída, então um cliente realmente saiu do refeitório naquele momento; se um cartão descreve um evento incerto, então um cliente realmente entrou ou saiu de um refeitório naquele momento.

O último caso de teste é seguido de uma linha contendo um único zero.

Saída

Para cada caso de teste seu programa deve imprimir uma única linha contendo um único inteiro, o número máximo de clientes que poderiam ter estado dentro dos refeitórios a qualquer momento.

Exemplo

Entrada:
4
07:22:03 X
07:13:22 E
08:30:51 E
21:59:02 X
4
09:00:00 E
20:00:01 X
09:05:00 ?
20:00:00 ?
8
10:21:00 E
10:25:00 X
10:23:00 E
10:24:00 X
10:26:00 X
10:27:00 ?
10:22:00 ?
10:20:00 ?
0

Saída:
1
2
4