DCEPC13A - The Next Number

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

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

hide comments
2023-04-27 14:52:08 [Rampage] Blue.Mary
No, I think the logic is very simple. It's not enough to be in classical.
2023-04-27 09:19:21 Simes
Interesting enough to be in classical.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.