A 쌍 만들기

양의 정수 한 쌍을 만들려고 한다. 이를 위해 사용할 십진 숫자 목록이 주어진다. 목록의 모든 숫자를 정확히 한 번씩 사용해야 하지만, 첫 번째 정수에 사용할 숫자와 두 번째 정수에 사용할 숫자는 선택할 수 있다. 또한 각 정수 안에서 숫자의 순서를 선택할 수 있지만, 어느 정수에서도 최상위(가장 왼쪽) 자리에 영을 놓을 수 없다. 또한 한 정수를 영 하나만으로 구성할 수도 없는데, 그러면 양수가 아니기 때문이다.

예를 들어, 목록 $[1, 0, 2, 0, 4, 3]$이 주어질 수 있다. 만들 수 있는 유효한 쌍 중 두 개는 $(200, 143)$와 $(3, 12400)$이다. 반면 다음 쌍들은 유효하지 않다.

• $(0102, 34)$: 앞에 영이 있다.

• $(0, 12340)$: 양수가 아닌 정수가 있다.

• $(10, 243)$와 $(12300, 47)$: 각 쌍에 포함된 숫자 목록이 주어진 숫자 목록과 정확히 같지 않다.

사용할 숫자 목록이 주어질 때, 만들 수 있는 두 정수 사이의 절댓값 차이의 최솟값은 얼마인가?

제한

시간 제한: 5초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{D}$의 각 문자는 십진 숫자이다. $\mathbf{D}$의 문자 중 적어도 두 개는 0가 아니다.

테스트 세트 1 (결과 공개)

$2 \le$은 $\mathbf{D} \le 8$의 길이이다.

테스트 세트 2 (결과 공개)

$2 \le$은 $\mathbf{D} \le 36$의 길이이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 줄이 주어진다. 각 줄은 하나의 숫자 문자열 $\mathbf{D}$로 테스트 케이스를 설명한다. $\mathbf{D}$의 각 문자는 반드시 사용해야 하는 숫자이다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 위 규칙에 따라 $\mathbf{D}$로 만든 두 정수 사이에서 가능한 절댓값 차이의 최솟값이다.

만들 수 있는 최적의 정수 쌍은 예제 케이스 #1에서는 $31$와 $24$, 예제 케이스 #2에서는 $10$와 $10$, 예제 케이스 #3에서는 $700$와 $80$, 예제 케이스 #4에서는 $89$와 $90$이다.