描述

背景

汤姆是一支精锐部队的新兵。作为他期末考试的最后一部分，他将被置于未知地形中，并且必须携带所有沉重的军事装备找到前往指定出口的路。

由于汤姆有点害怕这项任务，他利用谷歌地图获取了训练区域的卫星图像。他已经确定了所有可能的入口和出口地点，以及它们之间可能的连接和预估距离。由于不同的地形高度，地点之间的这种连接关系不一定是对称的。

然而，他不知道自己将从哪个地点行军到哪个地点。不幸的是，他很快意识到，无论自己如何刻苦训练，在距离最远的两个地点之间进行行军的这种最坏情况下，他都无法成功完成任务。

常识告诉他，教官们总是会选择不同的地点作为入口和出口，并且他认为每一对不同的地点成为他的任务的概率是相等的。

问题

给定一组地点、部分地点之间可能的连接及其长度，以及汤姆期望的成功概率$p$，假设每一对不同的地点被选中的可能性相同，你需要计算出汤姆必须适应的最小距离，以便他至少有概率$p$通过考试。

输入

第一行包含测试用例的数量。

接下来一行包含一个整数$p$（$1 \leq p \leq 100$），指定汤姆的最小成功概率。然后是一行包含地点数量$n$（$2 \leq n \leq 100$）。随后的$n$行，每行包含$n$个整数，用空格分隔。第$i$行包含从地点$i$到其他所有地点的距离，例如，从地点$i$到地点$j$的距离可以在第$i$行第$j$个位置找到。距离是非负整数，小于$1000$。一个地点到自身的距离始终为零。如果两个地点之间的距离是“$-1$”，则表示在相应方向上这两个地点之间没有直接连接。你可以假设每个地点都能以某种方式从其他任何地点到达。

输出

每个测试用例的输出以一行“Scenario #i:”开头，其中$i$是从$1$开始的测试用例编号。

然后打印一行，包含汤姆必须训练达到的最小距离，之后输出一个空行。

输入数据1

2
67
3
0 1 2
1 0 3
2 3 0
50
4
0 1 -1 -1
-1 0 1 999
1 -1 0 -1
-1 999 -1 0

输出数据1

Scenario #1:
3

Scenario #2:
2

来源

2005年德国达姆施塔特工业大学编程竞赛（训练赛）