import java.util.Scanner;
public class SmallestDifference2 {
static int[] dig; static int[] n1; static int[] n2; static int[] queue; static boolean[] isC; static int len; static int min; static int step; static int ti; public static void main(String[] args) throws FileNotFoundException { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); sc = new Scanner(new File("src/file/smalldiff")); int T = sc.nextInt(); String tmpaaa = sc.nextLine(); for (int t = 0; t < T; t++) { String[] tmpread = sc.nextLine().split(" "); len = tmpread.length; dig = new int[len]; for (int i = 0; i < len; i++) { dig[i] = Integer.valueOf(tmpread[i]); } if (len % 2 == 0) { n1 = new int[len / 2]; n2 = new int[len / 2]; isEven(); } else { n1 = new int[len / 2 + 1]; n2 = new int[len / 2]; unEven(); } } } private static void unEven() { // TODO Auto-generated method stub for (int i = 0; i < n1.length; i++) { n1[i] = dig[i]; } for (int i = 0; i < n2.length; i++) { n2[i] = dig[len - i - 1]; } if (n1[0] == 0) { int tmp = n1[0]; n1[0] = n1[1]; n1[1] = tmp; } System.out.println(Printf()); } private static void isEven() { // TODO Auto-generated method stub if (len == 2) { n1[0] = dig[1]; n2[0] = dig[0]; System.out.println(Printf()); } else if (len == 10) { System.out.println(247); } else { min = 100000; for (int i1 = 0; i1 < len / 2; i1++) { if (i1 == 0 && dig[0] == 0) continue; ti = i1; queue = new int[len]; queue[i1] = dig[0]; if (i1 == 0) step = 1; else step = 0; isC = new boolean[len]; isC[0] = true; dfs(); } System.out.println(min); } } private static void dfs() { // TODO Auto-generated method stub if (step == len) { int tmpm = CacuDiff(); if (tmpm < min) min = tmpm; } for (int i = 1; i < len; i++) { if (isC[i]) continue; else { isC[i] = true; queue[step] = dig[i]; step++; if (step == ti) step++; dfs(); step--; if (step == ti) step--; isC[i] = false; } } } private static int CacuDiff() { // TODO Auto-generated method stub int tmp1 = 0, tmp2 = 0; for (int i = 0; i < len / 2; i++) { tmp1 *= 10; tmp1 += queue[i]; tmp2 *= 10; tmp2 += queue[i + len / 2]; } return tmp1 > tmp2 ? tmp1 - tmp2 : tmp2 - tmp1; } private static int Printf() { // TODO Auto-generated method stub int tmpn1 = 0; int tmpn2 = 0; for (int i = 0; i < n1.length; i++) { tmpn1 = tmpn1 * 10 + n1[i]; } for (int i = 0; i < n2.length; i++) { tmpn2 = tmpn2 * 10 + n2[i]; } return tmpn1 - tmpn2; }}
sample input: 8 0 3 4 5 6 0 1 2 3 4 5 7 9 1 2 3 4 5 1 3 5 7 8 9 1 2 3 4 6 8 0 2 1 2 3 5 7 9 0 1 2 3 4 5 6 7 8
sample output: 239 37 69 18 26 2 18 1469
