문제
지구상에 존재하는 모든 생명체는 여러가지 방법에 따라 분류가 된다.
가장 큰 그룹으로 분류하면 26종으로 분류가 가능하다고 한다. 그리고 각 그룹의 멤버들은 다시 26종으로 분류가 가능하다. 이렇게 최대 9단계까지 세부 분류가 될 수 있다.
이러한 단계를 나타낸다면 총 26^9의 서로 다른 종류의 생명체로 분류가 가능하고 그 단계를 알파벳 대문자로 표현할 수 있다. "AB"라면 가장 높은 단계의 분류가 'A'이고 두번째 단계가 'B'인 모든 생명체를 의미한다.
생명체를 연구하는 정올 박사는 어떤 무인도에서 서식하는 생명체의 연구를 하면서 생명체가 발견될 때마다 분류표에 넣고 있다. 그러다가 수시로 현재까지 발견된 특정 종의 개수를 알고 싶어 한다. 예를 들어 생명체 "ABC"와 "ABDF"가 있을때 "AB"종의 개수를 구하려고 하면 모두 "AB"그룹에 포함되므로 2가 된다. 알고리즘을 모르는 정올 박사를 위해 프로그램을 작성해 주자.
입력
첫째 줄에 테스트케이스의 개수를 나타내는 정수 T가 주어진다. (1≤T≤50)
각 테스트케이스마다 첫째 줄에 정올박사가 요구하는 연산의 횟수를 나타내는 정수 N이 주어진다. ( 1 ≤ N ≤ 1000 )
이후 N개의 줄에 걸쳐서 정올박사가 요구하는 연산의 정보가 순서대로 주어진다.
각 연산 정보는 한 개의 문자로 구성된 명령의 종류 C와 생명체의 분류를 나타내는 문자열 S가 공백을 사이에 두고 주어진다.
C가 'I'이면 정올 박사가 새로운 생명체를 발견하여 분류표에 저장하는 것이다.
C가 'O'이면 현재까지 저장된 생명체중 S그룹의 수를 묻는 것이다. S의 길이는 1 이상 9이하이다.
출력
예제1
3
6
IABCD
OA
IXXYAA
IILOVE
IILIKE
OILO
4
IASDF
IASDFG
OASDFGH
OASDF
6
IJUNGOL
OJ
IHANC
IHANG
OHANF
OH
11
02
102