Maximize Number By Changing One Digit

Given a string representing a non-negative integer, your task is to maximize the number by changing exactly one digit to any digit from 0 to 9. The operation should ensure that the resulting number is as large as possible. If no single-digit change can improve the number (i.e. the number already consists of all 9's), then the original number should be returned.

Note: The number is given as a string to accommodate very large integers. The comparisons and modifications are done lexicographically, but note that the input is guaranteed to be a non-negative integer with no leading zeros (except for the single zero case).

Formally, let \( s \) be the original string. You are allowed to change the digit at exactly one position \( i \) (where \( 0 \leq i < |s| \)) to any digit \( d \) (where \( 0 \leq d \leq 9 \)). Among all possible outcomes, output the maximum string \( s' \) such that \( s' \) represents the maximum possible integer.

inputFormat

The first line contains an integer \( T \), the number of test cases. Each of the following \( T \) lines contains a non-negative integer represented as a string.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the maximum number (as a string) obtained by changing exactly one digit. The output is written to standard output (stdout).

## sample

3
123
555
809

923
955
909

</p>