描述

国际鸟类学家联盟的鸟类计算任务致力于研究鸟类的智力，特别是计算能力。到目前为止，最有前景的项目之一是由阿尔伯特·B·特罗斯博士（Dr. Albert B. Tross）及其助手克利福德·斯沃洛（Clifford Swallow）和佩里·基特（Perry Keet）开展的关于鹦鹉智力的“波利多项式（Polly Nomial）”项目。在这个鸟类计算任务（ACM）中，鹦鹉被训练进行涉及整数、变量和简单算术运算符的简单多项式计算。

当向鹦鹉展示一个由具有非负整数系数和一个变量$x$的多项式组成的公式时，每只鹦鹉会使用一个特殊的由喙操作的个人数字助理（PDA），即“鹦鹉数字助理”，来敲出一系列用于计算该多项式的操作。这个 PDA 的操作方式很像计算器。它有标有以下符号的按键：从$0$到$9$的数字、符号$x$以及运算符$+$、$*$和$=$。（为了测试目的，阿尔伯特·B·特罗斯会在内部将$x$按键与一个整数常量关联起来，但鹦鹉看到的只是$x$。）

例如，如果向鹦鹉展示多项式

鹦鹉可能会敲出以下符号序列：

PDA 没有额外的内存，所以每个$*$或$+$操作都会应用于显示屏上之前的内容以及后续输入的任何操作数。如果多项式是

那么鹦鹉在计算$2x^2$的值时就无法“保存”$x^3$的值。相反，需要采用不同的操作顺序，例如：

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

一次计算的成本是按键的次数。在上述示例中，计算$x^3 + x + 11$的成本是$11$（$x$键按$4$次、$*$键按$2$次、$+$键按$2$次、数字$1$键按$2$次以及$=$键按$1$次）。碰巧的是，对于使用这个 PDA 的这个特定表达式，这是最小成本。

你要编写一个程序，为鹦鹉找到计算多个多项式表达式的最低成本方法。毕竟鹦鹉的脑子有限，它们会被最高次项系数不为$1$的多项式吓倒，所以总是会满足这个条件。

输入

输入由一系列行组成，每行包含一个多项式和一个$x$的值。每个多项式$a_nx^n + a_{n - 1}x^{n - 1} + \cdots + a_0$由其次数以及按$x$的降幂排列的非负系数$a_n, \cdots, a_0$表示，其中$a_n$始终为$1$。次数在$1$到$100$之间。在同一行中，系数后面跟着变量$x$的一个整数值，该值始终为$1$或$-1$。输入以包含值$0$ $0$的单行结束。

输出

对于每个多项式，打印多项式编号，然后是该多项式在给定整数值$x$处的值以及计算该多项式的最小成本；仿照示例输出的格式。

输入数据 1

3 1 0 1 11 1
3 1 0 2 11 -1
0 0

输出数据 1

Polynomial 1: 13 11
Polynomial 2: 8 11

来源

2003 年美国中东部地区竞赛