A number is called as a lucky number if its decimal representation contains only the lucky digits, 4 and 7. e.g. 47, 744, 4 are lucky numbers, whereas 5, 17, 467 are not.
Recently, Na2a found a magic stone. With the help of this stone, he can multiply a number by any lucky number. Also, the magic stone can be used any number of times (possibly zero or infinite number of times). For example, if initially he has the number 1, then he can get numbers like 28 (formed by 147), 14476 (formed as 14777*4) etc.
Na2a has N numbers in his bag which are denoted by array A. For each number Ai in his bag, he asks you to transform it to a number with maximum possible number of trailing zeroes by using Magic Stone. You have to find the smallest of such numbers, since there can be multiple numbers with the maximum possible number of trailing zeros.

Input

There is a single test case.
First line contains a single integer N as stated in the problem.
The second line contains N space-separated integers A1, A2, ... , AN where Ai denotes the i^th number in the bag.

Output

Output N lines, in which i^th line contains the answer corresponding to the number Ai.

Constraints

1 ≤ N ≤ 10^5
1 ≤ Ai ≤ 10^9

Example
Input:
2
2 15

Output:
2
60

Explanation
Example case 1. You can't get any number having zeros at the end multiplying 2 by lucky numbers.
Example case 2. You can multiply 15 by 4 and get 60, which has one trailing zero.

见题面

见题面