Goku

0

0 votes
Hard
Problem

    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 10.

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 10.

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

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?