Moist

Moist에게는 피겨 스케이팅 트레이딩 카드를 수집하는 취미가 있다. 그의 카드 컬렉션은 계속 늘어났고, 이제는 정리되지 않은 한 더미에 보관하기에는 너무 많아졌다. Moist는 필요할 때마다 원하는 카드를 빠르게 찾을 수 있도록 카드들을 알파벳순으로 정렬해야 한다.

문제는 Moist가 카드들을 집으려고 하면 계속 손에서 미끄러지고, 땀 때문에 카드가 영구적으로 손상되므로 실제로 카드를 집을 수 없다는 것이다. 몇몇 카드는 상당히 비싸다는 점도 유념하라. 정렬을 쉽게 하기 위해 Moist는 Dr. Horrible을 설득하여 정렬 로봇을 만들게 했다. 하지만 Dr. Horrible은 자신의 꽤 끔찍한 방식대로, 정렬 과정에서 트레이딩 카드 하나를 옮겨야 할 때마다 정렬 로봇이 Moist에게 $1의 요금을 청구하도록 만들었다.

Moist는 로봇의 정렬 방식이 매우 원시적이라는 사실을 알아냈다. 로봇은 카드 덱을 위에서 아래로 훑는다. 이전 카드보다 사전순으로 앞서는 카드를 발견할 때마다, 그 카드를 위쪽 카드 더미의 올바른 위치로 옮긴다. 이 작업에는 $1가 들며, 로봇은 다시 카드 덱의 아래쪽을 향해 훑으면서 카드 덱 전체가 위에서 아래까지 사전순으로 정렬될 때까지 카드를 하나씩 옮긴다.

공교롭게도 Moist는 거의 빈털터리지만, 트레이딩 카드를 정돈된 상태로 보관하는 것은 그의 비참한 삶에 남은 유일한 즐거움이다. 그는 로봇을 사용하여 카드 덱을 정렬하는 데 비용이 얼마나 드는지 알아야 한다.

제한

시간 제한: 테스트 세트당 60초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 각 이름은 문자와 공백 문자로만 구성된다. 각 이름은 최대 100개의 문자를 포함한다. 어떤 이름도 공백으로 시작하거나 끝나지 않는다. 같은 테스트 케이스에 동일한 이름이 두 번 이상 등장하지 않는다. 사전순으로 공백 문자가 가장 먼저 오고, 그다음에는 대문자, 그다음에는 소문자가 온다.

작은 데이터 세트

1 ≤ N ≤ 10.

큰 데이터 세트

1 ≤ N ≤ 100.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 하나의 정수 N이 포함된 줄로 시작한다. 다음 N개의 줄에는 카드 덱의 위에서 아래 순서대로 각각 피겨 스케이팅 선수의 이름이 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작한다), y는 Moist가 로봇을 사용하여 트레이딩 카드 덱을 정렬하는 데 드는 달러 금액이다.