Alice is a very brilliant student. He considers '4' and '7' as Magic numbers. The numbers containing only magic numbers are also magical. Given a magic number N ,he wants to know what could be the next magical number greater than the given number.

Input

First line of input contains number of test cases T. For each test case, there is exits only one line containing a magic number N.

Output

For each test case, output a single line containing the next greater magical number.

Constraints

1 ≤ T ≤ 1000
4 ≤ N ≤ 10^100

Example

Input:
2
4
47

Output:
7
74

见题面

见题面