Largest Beautiful Number

그렇다. 이것은 "beautiful" 수의 정의에 관한 또 다른 문제이다.

양의 정수 x의 선행 영이 없는 십진수 표현이 짝수 개의 자릿수를 포함하고, 이 표현을 순열로 재배열하여 회문으로 만들 수 있다면 x를 아름다운 수라고 하자. 예를 들어 4242는 4개의 자릿수를 포함하고 회문인 순열 2442가 존재하므로 아름다운 수이다.

양의 정수 s가 주어질 때, s보다 작은 가장 큰 아름다운 수를 구한다.

첫 번째 줄에는 풀어야 할 테스트 케이스의 수를 나타내는 정수 하나 t (1 ≤ t ≤ 105)가 주어진다.

이어서 t개의 줄이 주어진다. 각 줄은 하나의 테스트 케이스를 나타내며, 수 s의 십진수 표현인 문자열 하나를 포함한다. 이 문자열의 길이는 짝수이고, 선행 영을 포함하지 않으며, s보다 작은 아름다운 수가 적어도 하나 존재함이 보장된다.

모든 테스트 케이스에 걸친 s의 길이 합은 t 2·105을 초과하지 않는다.

각 테스트 케이스마다 s보다 작은 가장 큰 아름다운 수를 포함하는 한 줄을 출력한다(답이 존재함이 보장된다).