The ugly numbers are those which only have the number 2, 3 or 5 as prime factors.

The sequence shows the first 11 ugly numbers, for convenience 1 is included.

    1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 ...

Input

The input consists of several lines, the first is the number N (0 <= N <= 200) which means the number of values to insert, then follow the Ni values to be processed.

Output

For each N-th input case, the N-th ugly number of the series must be returned.

Example

Input:
5
6
1
4
8
20

Output:
6
1
4
9
36

Los números feos son aquellos los cuales solo tienen como factores primos a los numero 2,3 o 5.

La secuencia muestra los primeros 11 números feos, por conveniencia el 1 está incluido.

    1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 ...

Entrada

La entrada consiste en varias líneas, la primera es el numero  N (0 <= N <= 200) es cual quiere decir la cantidad de valores  a insertar, a continuación siguen los Ni valores que se quieren procesar.

Salida

Para cada Ni-esimo caso de entrada se debe mostrar el Ni-esimo número feo de la serie.

Ejemplo

Entrada:
5
6
1
4
8
20

Salida:
6
1
4
9
36