With the year coming to a close, you are in mood for some hard core partying! You head to your favourite club, Brainy Bar, but find that only people who are smart enough to solve a computation challenge are being allowed in.

The challenge is as follows: the guard will give you a number, and you have to answer with the smallest number the product of whose digits is at least the given number. The guard will continue asking the question for different numbers till he is convinced of your admissibility, and you have to answer before he rejects you out of impatience. Note that only positive integers in their decimal representations are involved.

Here's the catch, Brainy Bar being Brainy Bar, the numbers that the guard will ask will be HUGE! Your only hope for entry is coding up the challenge. Can you do it?

INPUT

The first line contains T, the number of questions the guard will ask.

For each question there is a number N in a separate line, the number the guard asks.

OUTPUT

For each question, print in a single line a positive integer in decimal representation representing the answer you will give to the guard.

CONSTRAINTS

Task 1: 60 marks

T = 5000

1 <= D <= 10000

Task 2: 20 marks

T = 100

1 <= D <= 10000

Task 3: 20 marks

T = 100000

1 <= D <= 10,

Here, D is the number of digits in the correct answer.

TIME LIMIT: 3 seconds

AUTHOR: Rishabh Ranjan

TESTER: Navneel Singhal