사전 게임

철자 타일로 단어를 만드는 스크래블과 달리, 이 게임에서는 단어를 부순다. 두 사람이 번갈아 한 수씩 둔다.

게임은 단어 사전 하나로 시작한다. 차례가 온 사람은 단어 하나를 고른다. 고른 단어가 사전에 들어 있을 필요는 없지만, 그 시점의 사전에 있는 단어 가운데 적어도 하나의 접두사와 같아야 한다.

고른 단어를 $W$라고 하자. $W$를 접두사로 가지는 사전의 단어는 모두 두 조각으로 잘린다.

1. 앞 조각은 $W$에서 마지막 글자를 뺀 부분이다.
2. 뒤 조각은 $W$의 마지막 글자부터 시작하는 나머지 부분이다.

뒤 조각은 버리고 앞 조각만 사전에 남긴다. $W$를 접두사로 가지지 않는 단어는 그대로 둔다. 앞 조각이 빈 문자열이면, 즉 $W$의 길이가 1이면 그 글자로 시작하는 단어는 사전에서 사라진다. 이렇게 바뀐 사전에서 상대가 같은 방식으로 다음 수를 둔다.

예를 들어 사전이 다음과 같다고 하자.

bangladesh
bangalore
band
bandana

첫 번째 사람이 bang을 고르면 사전은 이렇게 바뀐다.

ban
ban
band
bandana

둘 수 있는 수가 없는 사람이 진다. 두 사람이 모두 최선을 다해 둘 때 누가 이기는지 구하라.

여기에 더해 사전을 키워 가며 같은 질문에 답해야 한다. 사전에 단어를 하나 추가하는 연산이 $Q$번 주어지고, 추가할 때마다 그 시점의 사전으로 게임을 하면 1번과 2번 중 누가 이기는지 답한다. 추가한 단어는 지워지지 않는다. 한 테스트 케이스 안에서 앞서 추가한 단어는 계속 사전에 남아 있다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($T \le 10$)

각 테스트 케이스의 첫 줄에는 사전에 든 단어의 개수 $N$이 주어진다. ($0 < N \le 50000$)

다음 $N$개 줄에 사전의 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 40 이하이다. 같은 단어가 여러 번 나올 수 있다.

그다음 줄에 연산의 개수 $Q$가 주어진다. ($0 < Q \le 50000$)

다음 $Q$개 줄에 사전에 추가할 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 40 이하이다.

사전의 단어와 추가할 단어는 모두 알파벳 소문자로만 이루어지고, 길이는 1 이상이다.

각 테스트 케이스마다 먼저 Case k:를 출력한다. 여기서 $k$는 1부터 시작하는 테스트 케이스 번호다.

그다음 추가 연산마다 한 줄씩 출력한다. 그 단어까지 넣은 사전으로 게임을 했을 때 먼저 두는 사람이 이기면 1, 나중에 두는 사람이 이기면 2를 출력한다.