A. Вася и пароль
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для регистрации на сайте EatForces Вася придумал пароль — строку $$$s$$$. Пароль на сайте EatForces — это строка, состоящая из строчных и заглавных латинских букв, а также цифр.

Но так как EatForces заботится о безопасности своих пользователей, пароли пользователей должны содержать минимум одну цифру, минимум одну заглавную латинскую букву и минимум одну строчную латинскую букву. Например пароли «abaCABA12», «Z7q» и «3R24m» допустимы, а пароли «qwerty», «qwerty12345» и «Password» — нет.

Подстрока строки $$$s$$$ — строка $$$x = s_l s_{l + 1} \dots s_{l + len - 1} (1 \le l \le |s|, 0 \le len \le |s| - l + 1)$$$. $$$len$$$ — длина подстроки. Обратите внимание, что пустая строка так же считается подстрокой строки $$$s$$$, и имеет длину $$$0$$$.

Возможно, пароль, придуманный Васей, не соответствует правилам безопасности EatForces. Однако, так как Васе он очень нравится, он хочет заменить некоторую его подстроку на подстроку такой же длины таким образом, чтобы пароль удовлетворял описанным выше условиям. При том, данная операция должна быть совершена ровно один раз, а выбранная подстрока должна быть минимально возможной длины.

Обратите внимание, что длина строки $$$s$$$ после замены подстроки не должна измениться, а сама строка должна состоять только из строчных и заглавных латинских букв, а также цифр.

Входные данные

В первой строке задано целое число $$$T$$$ ($$$1 \le T \le 100$$$) — количество тестов.

Следующие $$$T$$$ строк содержат изначальный пароль $$$s~(3 \le |s| \le 100)$$$, состоящий из строчных и заглавных латинских букв, а также цифр.

Для взломов разрешается только $$$T = 1$$$.

Выходные данные

Для каждого теста в отдельной строке выведите новый пароль, который удовлетворяет описанным выше условиям.

Длина замененной подстроки подсчитывается следующим способом: выпишем все измененные позиции. Если таких нет, то длина равна $$$0$$$. В противном случае длина равна разности первой и последней измененной позиции плюс один. Например, длина измененной подстроки между паролями "abcdef" $$$\rightarrow$$$ "a7cdEf" равна $$$4$$$, потому что измененные позиции — это $$$2$$$ и $$$5$$$, соответственно, длина $$$(5 - 2) + 1 = 4$$$.

Гарантируется, что всегда существует подходящий пароль.

Если существует несколько подходящих паролей, разрешается вывести любой из них.

Пример
Входные данные
2
abcDCE
htQw27
Выходные данные
abcD4E
htQw27
Примечание

В первом тестовом примере в Васином пароле не хватает цифры, он заменяет подстроку «C» на «4», и получает пароль «abcD4E». Таким образом, он заменил подстроку длины 1.

Во втором тестовом примере Васин пароль изначально подходящий, и ничего не нужно менять. Таким образом, мы заменили подстроку длины 0 (пустую подстроку).