22554_PollyNomials

The Avian Computation Mission of the International Ornithologists Union is dedicated to the study of intelligence in birds, and specifically the study of computational ability. One of the most promising projects so far is the "Polly Nomial" project on parrot intelligence, run by Dr. Albert B. Tross and his assistants, Clifford Swallow and Perry Keet. In the ACM, parrots are trained to carry out simple polynomial computations involving integers, variables, and simple arithmetic operators.
When shown a formula consisting of a polynomial with non-negative integer coe±cients and one variable x, each parrot uses a special beak-operated PDA, or "Parrot Digital Assistant," to tap out a sequence of operations for computing the polynomial. The PDA operates much like a calculator. It has keys marked with the following symbols: the digits from 0 through 9, the symbol 'x', and the operators '+', 'x', and '='. (The x key is internally associated with an integer constant by Al B. Tross for testing purposes, but the parrot sees only the 'x'.)
For instance, if the parrot were presented with the polynomial

x³ + x + 11

the parrot might tap the following sequence of symbols:

x , x , x , x , x , + , x , + , 1 , 1 , =

The PDA has no extra memory, so each  x  or  +  operation is applied to the previous contents of the display and whatever succeeding operand is entered. If the polynomial had been

x³ + 2x² + 11

then the parrot would not have been able to "save" the value of x³ while calculating the value of 2x². Instead, a different order of operations would be needed, for instance:

x , + , 2 , x , x , x , x , + , 1 , 1 , =

The cost of a calculation is the number of key presses. The cost of computing x³+x+11 in the example above is 11 (four presses of the x key, two presses of 'x', two presses of '+', two presses of the digit '1', and the '=' key). It so happens that this is the minimal cost for this particular expression using the PDA.
You are to write a program that finds the least costly way for a parrot to compute a number of polynomial expressions. Because parrots are, after all, just bird-brains, they are intimidated by polynomials whose high-order coefficient is any value except 1, so this condition is always imposed.