환영 파티

애자일 크리스털 마이닝은 여러 해 동안 학생 인턴 프로그램을 운영했다. 이 회사는 인턴이 스스로 팀을 꾸리는 능력을 높이 샀고, 그래서 오리엔테이션에서 서로 알아가는 활동으로 팀 나누기를 시켰다. 규칙은 하나다. 한 팀에 속한 사람은 이름의 첫 글자가 모두 같거나, 성의 첫 글자가 모두 같아야 한다. 여기에 조건을 하나 더 붙여서 재미를 더했다. 팀 수는 가능한 한 적어야 한다.

어느 해에는 인턴이 여섯 명이었다. Stephen Cook, Vinton Cerf, Edmund Clarke, Judea Pearl, Shafi Goldwasser, Silvio Micali. 이 여섯 명은 세 팀으로 나뉘었다.

• Stephen Cook, Vinton Cerf, Edmund Clarke: 성이 모두 C로 시작한다.
• Shafi Goldwasser, Silvio Micali: 이름이 모두 S로 시작한다.
• Judea Pearl: 재미있는 팀은 아니지만, 이 팀에 있는 사람의 이름은 전부 J로 시작한다.

참고로 이 회사는 결국 문을 닫았다. 성이 S, T, U, V, W, X, Y, Z로 시작하는 인턴은 뽑지 않는, 이상하고 불법적인 채용 관행 때문이었다. 이름에는 그런 기준을 적용하지 않았고, 덕분에 Vinton Cerf는 무사했다.

한 해의 인턴 명단이 주어지면, 필요한 팀 수의 최솟값을 구하라.

각 해의 인턴 명단이 테스트 케이스 하나다. 테스트 케이스의 첫 줄에는 그해 인턴 수 $N$ ($1 \le N \le 300$)이 주어진다. 이어지는 $N$개 줄에는 인턴 한 명의 이름과 성이 공백 하나를 사이에 두고 주어진다. 이름과 성에는 문장 부호가 없고, 둘 다 대문자로 시작한다. 성의 첫 글자는 항상 'A'와 'R' 사이다. 입력의 마지막 줄에는 0 하나만 있다. 테스트 케이스는 최대 20개다.

각 테스트 케이스마다 필요한 팀 수의 최솟값 $k$를 한 줄에 하나씩 출력한다.