파일 고치기

On Unix 컴퓨터에서는 데이터가 디렉터리에 저장된다. 루트 디렉터리가 하나 있으며, 그 안에는 이름이 서로 다른 여러 디렉터리가 들어 있을 수 있다. 이 디렉터리들 안에는 또 더 많은 디렉터리가 들어 있을 수 있고, 이런 식으로 계속된다.

디렉터리는 이름과 부모 디렉터리(그 디렉터리가 직접 들어 있는 디렉터리)로 유일하게 식별된다. 이는 일반적으로 경로로 표현되며, 경로는 각각 앞에 슬래시('/')가 붙은 여러 부분으로 구성된다. 마지막 부분은 디렉터리의 이름이고, 나머지 모든 부분은 부모 디렉터리의 경로를 나타낸다. 예를 들어 다음 경로를 살펴보자.

/home/gcj/finals

이는 "/home/gcj"이 나타내는 디렉터리 안에 있는, 이름이 "finals"인 디렉터리를 가리킨다. 그리고 전자는 다시 경로 "/home"이 나타내는 디렉터리 안에 있는, 이름이 "gcj"인 디렉터리를 가리킨다. 이 경로에는 부분이 하나뿐이므로, 루트 디렉터리 안에 있는 이름이 "home"인 디렉터리를 가리킨다.

디렉터리를 만들려면 mkdir 명령어를 사용할 수 있다. 경로를 지정하면 mkdir은 그 경로가 나타내는 디렉터리를 생성하지만, 부모 디렉터리가 이미 존재할 때만 생성한다. 예를 들어 "/home/gcj/finals" 및 "/home/gcj/quals" 디렉터리를 아무것도 없는 상태에서 만들려면 다음과 같이 네 개의 명령어가 필요하다.

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

컴퓨터에 이미 존재하는 디렉터리 전체와, 아직 존재하지 않는 경우 새로 만들려는 디렉터리 집합이 주어질 때, mkdir 명령어를 몇 개 사용해야 하는가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 어떤 경로도 100자를 초과하지 않는다. 컴퓨터에 이미 존재하는 디렉터리 목록이나 만들려는 디렉터리 목록에서 같은 경로가 두 번 나타나지 않는다. 단, 하나의 경로가 두 목록 모두에 한 번씩 나타날 수는 있다. (아래 예제 케이스 #2을 참고하라.) 어떤 디렉터리가 컴퓨터에 존재한다고 목록에 주어지면, 부모 디렉터리가 루트 디렉터리인 경우를 제외하고 그 부모 디렉터리도 목록에 주어진다. 입력 파일의 전체 길이는 100,000바이트를 초과하지 않는다.

작은 데이터 세트 (테스트 세트 1 - 공개)

0 ≤ N ≤ 10. 1 ≤ M ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

0 ≤ N ≤ 100. 1 ≤ M ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 케이스는 공백으로 구분된 두 정수 N과 M이 포함된 줄로 시작한다.

다음 N개의 줄에는 각각 컴퓨터에 이미 존재하는 디렉터리 하나의 경로가 주어진다. 이 목록에는 루트 디렉터리를 제외하고 컴퓨터에 이미 존재하는 모든 디렉터리가 포함된다. (루트 디렉터리는 모든 컴퓨터에 있으므로 명시적으로 나열할 필요가 없다.)

다음 M개의 줄에는 각각 만들려는 디렉터리 하나의 경로가 주어진다.

입력의 각 경로는 위 문제 설명에 나온 형식으로 주어진다. 구체적으로 경로는 하나 이상의 소문자 영숫자 문자열(즉, 'a'-'z' 및 '0'-'9' 기호만 포함하는 문자열)로 구성되며, 각 문자열 앞에는 슬래시 하나가 붙는다. 이 영숫자 문자열들은 절대 비어 있지 않다.

각 테스트 케이스마다 "Case #x: y"이 포함된 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 필요한 mkdir의 개수이다.