In the town of wizards, Mario is the best magician. He is known for his tricks with numbers. Magician Luigi is jealous of Mario's popularity. So he challenged Mario to perform the following trick. Given a number N find the greatest lucky number K such that K<=N. A number is lucky if it contains only 1 and 3. Magician Mario is a little confused, so he called you, a programmer, for his help to find the required lucky number.

INPUT

First line of input contains a number T, the number of test cases. Each of the next T line contains a number N.

OUTPUT

For each N, print its corresponding lucky number in a new line.

CONSTRAINTS

T<=100
N >=1
No of digits in N <= 100