솔리테어

Maggie는 특별한 카드 덱을 가지고 있다. 덱에는 카드가 $4n$장 있다. $1$부터 $n$까지의 각 $i$에 대해 값이 $i$인 카드가 네 장씩 있는데, 스페이드, 하트, 다이아몬드, 클럽의 $i$가 하나씩이다. Maggie는 이 덱으로 간단한 솔리테어 게임을 한다.

게임을 시작할 때 덱은 뒷면이 위로 가도록 탁자에 놓인다. 무늬마다 빈 슬롯이 하나씩 네 개 있고, 덱 옆에는 빈 버림 더미가 있다. 목표는 모든 무늬의 카드를 그 무늬의 슬롯에 올려놓는 것이다. 카드는 오름차순으로 슬롯에 놓아야 한다. 자세한 규칙은 다음과 같다.

게임 중 Maggie는 다음 단계를 반복한다.

1. 덱의 맨 위 카드를 집는다.
2. 카드의 무늬를 확인하고, 그 무늬에 해당하는 슬롯을 본다.
3. 카드가 에이스(값이 $1$)이면 빈 슬롯에 놓는다.
4. 카드의 값 $v$가 $1$보다 크고, 해당 슬롯의 맨 위 카드의 값이 $v-1$이면, 값이 $v$인 카드를 값이 $v-1$인 카드 위에 놓을 수 있다. 예를 들어 스페이드 8은 스페이드 7 위에 놓을 수 있다.
5. 현재 카드를 슬롯에 놓을 수 없으면, 앞면이 위로 가도록 버림 더미에 놓는다. 예를 들어 현재 카드가 스페이드 8이고 스페이드 슬롯의 맨 위 카드가 스페이드 3이면, 스페이드 8은 버림 더미로 간다.
6. 덱에 카드가 남아 있지 않다면: 버림 더미에도 카드가 없으면(즉 $4n$장 모두 슬롯에 놓였으면) 게임이 끝난다. 그렇지 않으면 버림 더미를 뒤집어 새 덱을 만든다. 새 덱에서 카드의 순서는 원래 덱에서의 상대적인 순서와 같다.

Maggie는 결국 반드시 이기지만, 시간이 꽤 오래 걸릴 때도 있다.

입력으로 $n$과 덱에 있는 카드의 초기 순서가 주어진다. Maggie가 이기기 전까지 덱을 몇 번 돌았는지 구하라. 답은 버림 더미를 뒤집어 새 덱을 만든 횟수에 1을 더한 값이다.

첫 줄에는 테스트 케이스의 개수 $t$가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.

각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 정수 $n$이 주어진다. 둘째 줄에는 서로 다른 $4n$장의 카드가 위에서 아래 순서로 주어진다. 각 카드는 Xy 형식이며, $X$는 네 무늬 중 하나이고 $y$는 값이다. 예를 들어 H47은 하트 47이다.

각 테스트 케이스마다 Maggie가 이기기까지 덱을 몇 번 돌아야 하는지 정수 하나를 한 줄에 출력한다.

덱을 한 번 돈 뒤 네 슬롯의 맨 위 카드는 스페이드 1, 하트 2, 다이아몬드 2, 클럽 3이 된다. 나머지 카드는 버림 더미에 있다. 그다음 Maggie는 버림 더미를 뒤집고, 스페이드 2부터 다시 시작해서 남은 카드를 한 번 더 돈다. 이 두 번째 순회에서 남은 카드를 모두 놓을 수 있다.