이어 붙이기 정렬

정수 목록 $\mathbf{X_1}, \mathbf{X_2}, \dots, \mathbf{X_N}$이 있다. 이 정수들을 엄격한 오름차순으로 만들고 싶지만, 안타깝게도 순서를 바꿀 수 없다. 이는 일반적인 정렬 알고리즘이 작동하지 않는다는 뜻이다.

유일한 방법은 각 정수의 오른쪽에 숫자 $0$부터 $9$까지를 이어 붙여서(밑이 $10$인 진법으로) 정수를 바꾸는 것이다. 예를 들어 정수 중 하나가 $10$이면, 한 번의 이어 붙이기 연산으로 이를 $10\textbf{0}$ 또는 $10\textbf{9}$으로 만들거나, 두 번의 연산으로 $10\textbf{34}$로 만들 수 있다(아래 이미지 참조).

현재 목록이 주어질 때, 목록을 엄격한 오름차순으로 만드는 데 필요한 한 자리 숫자 이어 붙이기 연산의 최소 횟수는 얼마인가?

예를 들어 목록이 $100, 7, 10$이면, 다음 이미지와 같이 총 $4$번의 연산을 사용하여 정렬된 목록으로 만들 수 있다.

제한

시간 제한: 10초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$.

테스트 세트 1 (Visible Verdict)

$2 \le \mathbf{N} \le 3$. 모든 $i$에 대해 $1 \le \mathbf{X_i} \le 100$.

테스트 세트 2 (Visible Verdict)

$2 \le \mathbf{N} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{X_i} \le 10^9$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 설명된다. 테스트 케이스의 첫 번째 줄에는 목록에 있는 정수의 개수를 나타내는 하나의 정수 $\mathbf{N}$이 주어진다. 두 번째 줄에는 목록의 원소인 $\mathbf{N}$개의 정수 $\mathbf{X_1}, \mathbf{X_2}, \dots, \mathbf{X_N}$이 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$은 목록을 엄격한 오름차순으로 만드는 데 필요한 한 자리 숫자 이어 붙이기 연산의 최소 횟수이다.

예제 케이스 #1의 입력은 문제 설명에 제시된 예와 같다. 이미지에서 볼 수 있듯이, 목록은 $4$번의 연산으로 정렬된 목록이 될 수 있다. 마지막 두 정수는 최종적으로 적어도 $3$자리여야 한다는 점에 유의하라(총 적어도 $3$번의 이어 붙이기 연산이 필요하다). 최종 수가 모두 정확히 세 자리라면, 두 번째 수는 $1$ 대신 $7$로 시작하므로 세 번째 수보다 클 것이다. 이는 $4$번보다 적은 연산으로는 해낼 수 없다는 뜻이다.

예제 케이스 #2에서는 목록이 엄격한 오름차순이어야 하므로 적어도 한 번의 연산을 해야 한다는 점에 유의하라. 이 경우 두 번째 정수에 대한 유효한 이어 붙이기 연산은 어느 것이든 가능하다.

예제 케이스 #3에서는 두 번의 이어 붙이기 연산을 사용하여 목록을 $4, 19, 1\textbf{93}$로 만들 수 있다.

예제 케이스 #4에서는 주어진 목록이 이미 엄격한 오름차순이므로 연산이 필요하지 않다.