DCEPC13A - The Next Number

no tags 

Rishabh is obsessed with numbers 6 and 9. So he wants to find the next greatest number for every number using the digits 6 and 9 only.

Help him accomplish his task.

Input

The first line contains T number of test cases.

Each line contains a number N as input.

Output

Output T lines containing the next greatest number.

Constraints

1 ≤ T ≤ 100

1 ≤ N ≤ 101000

Example

Input:
4
34
555
67
6

Output:
66
666
69
9

hide comments
[Rampage] Blue.Mary: 2023-04-27 14:52:08

No, I think the logic is very simple. It's not enough to be in classical.

Simes: 2023-04-27 09:19:21

Interesting enough to be in classical.


Added by:dce coders
Date:2015-03-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:dce_coders