Rise and Fall

어떤 수의 십진수 표현을 두 부분(빈 부분이어도 된다)으로 나눌 수 있고, 첫 번째 부분의 자릿수가 비감소 순서이고 두 번째 부분의 자릿수가 비증가 순서이면 그 수를 Rise and Fall하다고 한다.

입력으로 주어진 수 이하이면서 Rise and Fall한 수 중 가장 큰 수를 구하라.

첫째 줄에는 정수 $t$ ($1 \le t \le 10^5$)가 주어지며, 이는 테스트 케이스의 수이다.

다음 $t$개의 줄에는 각각 정수 $n$ ($1 \le n < 10^{100{,}000}$)이 주어진다. 각 줄이 하나의 테스트 케이스이다.

• 참고: 오타가 아니다. 정수는 최대 $10^5$자리일 수 있다.

모든 입력 테스트 케이스의 길이의 합은 $10^5$을 넘지 않는다.

각 테스트 케이스마다, 해당 테스트 케이스의 $n$ 이하이면서 Rise and Fall한 수 중 가장 큰 수를 한 줄에 하나씩 출력한다.