When you enter 8 numbers from 0 to 9, write a program that outputs the difference between the largest integer and the smallest integer that can sort the 8 numbers. The number that can be sorted may start from 0, such as 00135569.



Input

Given multiple datasets. The number of datasets n (n ≤ 50) is given on the first line. Then n rows of data are given. Each data is a sequence of 8 numbers (0 to 9 numbers).

Output

For each dataset, output the difference between the largest and smallest integers that can be rearranged in the entered numbers on one line.

Example

Input

2
65539010
65539010


Output

96417531
96417531
import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        input.nextLine();
        for(int i = 0 ; i < n ; i++){
            int[] number = new int[10];
        	String s = input.nextLine();

        	for(int j = 0 ; j < s.length(); j++){
        		number[s.charAt(j)-48]++;
        	}

        	String min = "";

        	for(int j = 0 ; j < number.length ; j++){
        		while(number[j] != 0){
        			min += j;
        			number[j]--;
        		}
        	}

        	String max = "";

        	for(int j = 0 ; j < s.length(); j++){
        		number[s.charAt(j)-48]++;
        	}

        	for(int j = number.length-1 ; j >= 0 ; j--){
        		while(number[j] != 0){
        			max += j;
        			number[j]--;
        		}
        	}
        	System.out.println(Integer.parseInt(max)-Integer.parseInt(min));
        }
    }
}