Product trees P30012

Let a product tree be a binary tree such that every internal node is the product of its two children. For instance, these are some product trees with external nodes 1, 2, 3, 4 and 5:

$$\begin{array}[3]{ccc} \pstree[levelsep=25pt,treesep=12pt] {\Tcircle{\mbox{\scriptsize 120}}}{ \pstree{\Tcircle{\mbox{\scriptsize 24}}} { \pstree{\Tcircle{\mbox{\scriptsize 6}}} { \pstree{\Tcircle{\mbox{\scriptsize 2}}} { \Tcircle{\mbox{\scriptsize 1}} \Tcircle{\mbox{\scriptsize 2}} } \Tcircle{\mbox{\scriptsize 3}} } \Tcircle{\mbox{\scriptsize 4}} } \Tcircle{\mbox{\scriptsize 5}} } & \qquad \qquad \pstree[levelsep=25pt,treesep=12pt] {\Tcircle{\mbox{\scriptsize 120}}}{ \Tcircle{\mbox{\scriptsize 1}} \pstree{\Tcircle{\mbox{\scriptsize 120}}} { \pstree{\Tcircle{\mbox{\scriptsize 60}}} { \Tcircle{\mbox{\scriptsize 3}} \pstree{\Tcircle{\mbox{\scriptsize 20}}} { \Tcircle{\mbox{\scriptsize 5}} \Tcircle{\mbox{\scriptsize 4}} } } \Tcircle{\mbox{\scriptsize 2}} } } & \qquad \quad \pstree[levelsep=25pt,treesep=12pt] {\Tcircle{\mbox{\scriptsize 120}}}{ \pstree{\Tcircle{\mbox{\scriptsize 20}}} { \Tcircle{\mbox{\scriptsize 4}} \Tcircle{\mbox{\scriptsize 5}} } \pstree{\Tcircle{\mbox{\scriptsize 6}}} { \Tcircle{\mbox{\scriptsize 3}} \pstree{\Tcircle{\mbox{\scriptsize 2}}} { \Tcircle{\mbox{\scriptsize 1}} \Tcircle{\mbox{\scriptsize 2}} } } } \end{array}$$

Let us define the cost of a tree as the product of all its nodes. For the trees above, the costs are $120 * 24 * 5 * 6 * 4 * 2 * 3 * 1 * 2 = 4147200$, $120 * 1 * 120 * 60 * 2 * 3 * 20 * 5 * 4 = 2073600000$, and $120 * 20 * 6 * 4 * 5 * 3 * 2 * 1 * 2 = 3456000$.

Which is the minimum cost for a product tree, given a list of its external nodes?

Input

Input consists of a sequence of cases. Every case begins with $n$, followed by $n$ real numbers between 1 and 10. Assume $1 \le n \le 1000$. A special case with $n = 0$ ends the input.

Output

For every case, print a line with the minimum cost for a product tree with the given external nodes. Print only the integer part of the result. If the result has more than seven digits, print only its most significant seven digits. The input is such that the result always fits into a double, and such that there are no precission issues.