Append Sort

정수 리스트 $X_1, X_2, \dots, X_N$이 있다. 이 리스트를 강한 증가 순서로 만들고 싶지만, 원소의 순서를 바꿀 수는 없다. 따라서 일반적인 정렬 알고리즘은 쓸 수 없다.

유일한 방법은 각 정수의 오른쪽에 0부터 9까지의 숫자를 덧붙이는 것(10진법)이다. 예를 들어 정수 10은 한 번의 추가 연산으로 100이나 109로 만들 수 있고, 두 번의 연산으로 1034로 만들 수 있다(아래 그림 참조).

주어진 리스트에 대해, 리스트를 강한 증가 순서로 만드는 데 필요한 최소 한 자리 추가 연산 횟수를 구하라.

예를 들어 리스트가 100,7,10이면, 아래 그림처럼 총 4번의 연산으로 정렬된 리스트로 만들 수 있다.

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 테스트 케이스의 첫 줄에는 리스트에 있는 정수의 개수 $N$이 주어진다. 둘째 줄에는 리스트의 원소 $X_1, X_2, \dots, X_N$이 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 리스트를 강한 증가 순서로 만드는 데 필요한 최소 한 자리 추가 연산 횟수이다.

• $1 \le T \le 100$.

샘플 케이스 #1의 입력은 문제 지문의 예시와 같다. 그림에서 보듯이 리스트를 4번의 연산으로 정렬된 리스트로 만들 수 있다. 마지막 두 정수는 적어도 3자리로 끝나야 한다(총 최소 3번의 추가 연산이 필요하다). 만약 모든 최종 숫자가 정확히 세 자리라면, 두 번째 숫자가 1 대신 7로 시작하므로 세 번째 숫자보다 커진다. 따라서 4번보다 적은 연산으로는 만들 수 없다.

샘플 케이스 #2에서는 리스트가 강한 증가 순서여야 하므로, 적어도 한 번의 연산이 필요하다. 이 경우 두 번째 정수에 대한 유효한 추가 연산은 무엇이든 된다.

샘플 케이스 #3에서는 두 번의 추가 연산으로 리스트를 4,19,193으로 만들 수 있다.

샘플 케이스 #4에서는 주어진 리스트가 이미 강한 증가 순서이므로 연산이 필요 없다.