Рабочее место участника

Клапауций любит счастливые числа. Они приносят ему удачу. В рулетку он ставит только на счастливые номера – 7, 22, 00 и другие. Его номер телефона 7634295 также является счастливым числом. Когда Клапауций видит число, не являющееся счастливым, он старается переставить его цифры таким образом, чтобы получилось счастливое число. Его не интересует основание системы счисления, в котором записано число, он превращает в счастливые двоичные, десятичные, шестнадцатеричные и даже 36-ричные числа. Если Клапауцию не удается переставить цифры в числе для получения счастливого числа, он заменяет такое число текстом ALUCKYNUMBER.

Клапауций считает счастливыми числа, у которых сумма первых `[N/2]` цифр равна сумме `[N/2]` последних цифр, где `N` – количество цифр в числе.

Напишите программу, которая облегчит работу Клапауция по превращению всех чисел в счастливые.

Во входном файле в первой строке содержится целое число `K` (`1\ ≤\ K\ ≤\ 10`) – количество чисел в файле. Далее следует `K` строк, содержащих по одному числу в строке. Числа состоят из цифр от 0 до 9 и прописных латинских букв от A до Z. Буква A соответствует цифре 10, буква Z – цифре 35. Количество цифр в каждом числе не превышает 100.

В выходной файл вывести `K` строк с результатами для каждого числа входного файла. Если `i`-e число входного файла можно сделать счастливым, переставив его цифры, то в `i`-й строке выходного файла вывести один из вариантов (любой) такой перестановки. Если не существует счастливой перестановки цифр числа, то в `i`-й строке вывести текст ALUCKYNUMBER.

3
113
405808AF
123

131
84580A0F
ALUCKYNUMBER