题目描述

正如你们大多数人可能已经知道的那样，今天的英特尔级高科技处理器会执行一系列并行任务，以帮助加快指令执行。这些任务中最复杂的是分支预测。由于现代处理器上的指令块被分解为独立的块并执行以提高速度，因此总是需要预测执行路径将采用哪个分支（在评估条件以选择分支所需的实际操作数可用之前）。这项复杂的任务目前还没有得到充分的解决，但启发式（一如既往）有所帮助。

与实际的分支预测任务相比，我们现在要考虑的任务要简单得多。对于我们的建模，让我们假设每条指令都有以下语法：

所有标签都是字母字符串。标签区分大小写。

此外，某个分支被采用的概率是P（对所有分支都是相等的）。如果采用分支，则执行点（控制）将转到分支标签。否则，将执行该顺序中的下一个语句。控件从“start”（小写）标签开始，控件在“end”（大写）标签结束。开始和结束的分支标签本身就是，当执行开始时，控制将转到下一条指令，当执行结束时，处理以100%的概率结束。程序中的最后一句总是“结束（end）”。

需要找到语句执行的预期次数。

输入格式

T——测试用例的数量；

对于每个测试用例：

第一行包含一个整数N（后面的行数）、一个实数P和一个标签L。

以下N行中的每一行都由说明（两个标签）组成。

输出格式

对于每个测试用例，输出一行，其中包含：

“标签L被执行的预期次数为R”，

其中L-是输入中给出的标签

R-表示标签预计执行的次数。它必须精确地打印五位小数。

限制：

T<=20

3<=N<=120。

P介于0.01和0.99之间，即没有跳跃是100%确定的。

此外，您可以假设跳跃侧没有标签，而无需在整个程序中定义。

每个标签的长度小于10个字符。

此外，每行都有一个与之关联的独特标签。