A programmer from 1st yr (let's call him Goku) just started Competitive Programming. Goku wrote a random no generator code with seed 42 which prints values from 0-9. He found that the numbers 2 and 8 appeared the least. Now he likes the numbers which contain 2's and 8's only. For example, he likes 28, 228882, 822 but not 7,54,3689.
Now he ran the same Random no generator code 100 times, but this time with seed 54. This time he found, that all the numbers 0-9 appeared exactly 10 times, except 2 and 8 which appeared 8 and 12 times respectively. Now he loves the numbers which contains 2's and 8's equal no of times. For example, he loves 283, 1225889, 1345679, 8282 but not 228945, 8000, 2546.
Help him find the least number he likes as well as loves which is not less than N.
INPUT
First line contains a single integer denoting the number of test cases. No of test cases does not exceed 105 .
First line of each test contains a positive integer N (1<=N<=10100000 ). It is guarenteed that the sum of number of digits of all test cases does not exceed 106 .
OUTPUT
For each test case output the least number he likes as well as loves which is more than or equal to N.
Subtask 1 (20 pts) :- 1<=N<=106
Subtask 2 (20 pts) :- 1<=N<=1018
Subtask 3 (60 pts) :- Original Constraints