Polly Nomials

The International Ornithologists Union runs the Avian Computation Mission (ACM), which studies the computational ability of birds. In its most famous project, the "Polly Nomial" project, parrots are trained to evaluate simple polynomials in one variable $x$ with non-negative integer coefficients.

Each parrot uses a Parrot Digital Assistant (PDA), a beak-operated calculator. Its keys are the digits $0$ through $9$, the symbol $x$, and the operators $+$, $\times$, and $=$. The $x$ key stands for the variable; its numeric value is set internally for testing, but the parrot only ever sees the symbol $x$.

The PDA works like a basic immediate-execution calculator: it has NO extra memory and NO operator precedence. It evaluates strictly left to right, applying each $+$ or $\times$ immediately to the value currently on the display and the next operand that is entered. An operand is either the variable $x$ or a non-negative integer typed one digit at a time.

For example, to compute $x^3 + x + 11$ a parrot might press:

$x,\ \times,\ x,\ \times,\ x,\ +,\ x,\ +,\ 1,\ 1,\ =$

which evaluates as $((((x \times x) \times x) + x) + 11)$.

Because the PDA has no memory, the parrot cannot store a partial result. For a polynomial such as $x^3 + 2x^2 + 11$ it cannot first compute $x^3$ and set it aside while computing $2x^2$; it must instead choose an order of operations (for instance a nested, Horner-style scheme) that reaches the answer using only the single display.

The cost of a computation is the total number of key presses, including the final $=$. For $x^3 + x + 11$ the sequence above costs $11$: four presses of $x$, two of $\times$, two of $+$, two presses of the digit $1$, and one $=$. This happens to be the minimum possible cost for that polynomial.

Write a program that, for each given polynomial, reports its value at the given $x$ and the minimum possible key-press cost. Because parrots are intimidated by a leading coefficient other than $1$, the highest-degree coefficient is always $1$.

Each line describes one polynomial $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$. A line begins with the degree $n$ ($1 \le n \le 100$), followed by the $n+1$ non-negative coefficients $a_n, a_{n-1}, \ldots, a_0$ in order of decreasing power (with $a_n = 1$ always), and finally the integer value of $x$, which is always either $1$ or $-1$. The input ends with a line containing the two values 0 0, which must not be processed.

For each polynomial, print a line of the form Polynomial i: value cost, where i is the polynomial's position in the input (starting from $1$), value is the polynomial evaluated at the given $x$, and cost is the minimum number of key presses (including the final $=$) needed to compute it.