Степень эксцентричности числа
Вы думаете эксцентричным быть легко? Это не тот случай, когда Вы - число.
Степенью эксцентричности 2N-значного целого числа X (возможно с ведущими нулями) называется наименьшее возможное значение |a + b - 10^N| для некоторых N-значных целых чисел a и b (возможно с ведущими нулями) такое что S_d(X) = S_d(a) +S_d(b) имеет место для каждой цифры d, где S_d(P) (0 ≤ d ≤ 9) - количество вхождений цифры d в десятичное представление P. Например, степень эксцентричности забавных чисел (смотри задачу Подсчет забавных чисел) равна 0, а степень эксцентричности числа 192747 равна 7 (|274 + 719 - 1000| = 7).
Вам задан набор чисел четной длины. Найдите степень эксцентричности каждого из них.
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 1000). Каждая из следующих t строк содержит целое число четной длины (возможно с ведущими нулями). Общая длина всех чисел (кроме t) не превосходит 10^6.
Выходные данные
Для каждого теста вывести строку, содержащую степень эксцентричности соответствующего числа.