Moist의 카드 정렬

Moist는 피겨 스케이팅 트레이딩 카드를 모은다. 수집품이 계속 늘어나 한 뭉치로 아무렇게나 쌓아 두기에는 너무 많아졌다. 필요할 때 원하는 카드를 바로 찾으려면 카드 뭉치를 맨 위부터 맨 아래까지 사전순으로 정렬해야 한다.

문제는 Moist가 카드를 직접 집을 수 없다는 점이다. 카드가 손에서 자꾸 미끄러지고, 땀 때문에 카드가 영구히 상한다. 값이 꽤 나가는 카드도 섞여 있다. 그래서 Moist는 Dr. Horrible을 설득해 정렬 로봇을 만들게 했다. Dr. Horrible은 평소 성격대로 로봇이 카드를 한 장 옮길 때마다 $1을 받기로 정했다.

로봇의 정렬 방식은 단순하다. 로봇은 카드 뭉치를 위에서 아래로 훑어 내려간다. 바로 위 카드보다 사전순으로 앞서는 카드를 발견하면 그 카드를 빼내어 위쪽 더미의 알맞은 자리에 끼워 넣는다. 이 동작에 $1이 든다. 그런 다음 멈췄던 지점부터 다시 아래로 훑어 내려가며, 뭉치 전체가 위에서 아래로 사전순 정렬될 때까지 이 과정을 반복한다.

Moist는 거의 빈털터리이지만 카드를 정리해 두는 일만이 남은 낙이다. 각 카드 뭉치를 정렬하는 데 로봇이 얼마를 청구하는지 구하라.

첫 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 N이 하나 주어진다. 다음 N개의 줄에는 피겨 스케이팅 선수의 이름이 카드 뭉치의 맨 위부터 맨 아래 순서로 한 줄에 하나씩 주어진다.

제한

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 100.
• 이름은 알파벳 문자와 공백 문자로만 이루어진다.
• 이름의 길이는 최대 100자이다.
• 이름은 공백으로 시작하지 않고 공백으로 끝나지도 않는다.
• 같은 테스트 케이스 안에서 같은 이름이 두 번 나오지 않는다.
• 사전순에서는 공백 문자가 가장 앞서고, 그다음이 대문자, 그다음이 소문자이다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 그 카드 뭉치를 정렬하는 데 로봇이 청구하는 금액이다.