1860 年，驿马快递（Pony Express）是连接美国东西海岸最快的邮件投递系统。该系统服务于 $N$ 个不同的城市。每个城市都有一匹马（正如“一马当先”这个词所暗示的）；每匹马都以恒定的速度奔跑，并且在变得过于疲劳而无法继续之前，有一个最大总行驶距离。

驿马快递的骑手从出发城市的马开始骑行。每当骑手到达一个城市时，他们可以选择继续使用当前的马，或者换成该城市的马；换马是瞬间完成的。马永远没有休息的机会，所以每当一匹马的最大总行驶距离被“用掉”一部分时，它就永远被用掉了！当骑手到达目的地城市时，邮件即被送达。

城市之间的路线是通过公司所有者、立法者、工会代表和表亲 Pete 之间复杂的谈判建立的。这意味着城市之间的距离不一定符合常理：例如，它们不一定符合三角不等式，而且从城市 A 到城市 B 的距离可能与从城市 B 到城市 A 的距离不同！

你是一位时间旅行的企业家，从未来带来了一台快速计算机。单台计算机不足以让你建立电子邮件服务并使驿马快递过时，但你可以用它为驿马快递制定最优的路线规划。给定关于城市间路线和每个城市马匹的所有数据，以及一系列出发和到达城市对，你能快速计算出每次投递所需的最短时间吗？（你应该将所有这些投递视为独立的；在一条路线上使用城市/马匹不会使它们在其他路线上不可用。）

输入格式

输入的第一行给出了测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例描述如下：

• 一行包含两个整数：$N$，拥有马匹的城市数量，以及 $Q$，我们感兴趣的停靠点对数。城市编号从 $1$ 到 $N$。
• $N$ 行，每行包含两个整数 $E_i$（第 $i$ 个城市马匹的最大总行驶距离，单位为公里）和 $S_i$（该马匹奔跑的恒定速度，单位为公里/小时）。
• $N$ 行，每行包含 $N$ 个整数。第 $i$ 行的第 $j$ 个整数 $D_{ij}$ 表示从第 $i$ 个城市到第 $j$ 个城市的直接路线长度（单位为公里）；如果不存在直接路线，则为 $-1$。
• $Q$ 行，每行包含两个整数 $U_k$ 和 $V_k$，分别表示我们想要调查的第 $k$ 对城市的起点和终点。

输出格式

对于每个测试用例，输出一行，包含 Case #x: y1 y2 ... yQ，其中 $x$ 是测试用例编号（从 $1$ 开始），$y_k$ 是从城市 $U_k$ 到城市 $V_k$ 投递信件所需的最短时间（单位为小时）。

如果 $y_k$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则被视为正确。

数据范围

时间限制：每个测试集 20 秒。 内存限制：1 GB。 $1 \le T \le 100$。 $2 \le N \le 100$。 $1 \le E_i \le 10^9$，对于所有 $i$。 $1 \le S_i \le 1000$，对于所有 $i$。 $-1 \le D_{ij} \le 10^9$，对于所有 $i, j$。 $D_{ii} = -1$，对于所有 $i$。（不存在从城市到其自身的直接路线。） $D_{ij} \neq 0$，对于所有 $i, j$。 $U_k \neq V_k$，对于所有 $k$。 保证对于所有 $k$，从 $U_k$ 到 $V_k$ 的投递都可以通过给定的马匹完成。 $U_l \neq U_m$ 和/或 $V_l \neq V_m$，对于所有不同的 $l, m$。（在一个测试用例中，不会重复调查相同的有序城市对。）

样例

样例输入 1

3
3 1
2 3
2 4
4 4
-1 1 -1
-1 -1 1
-1 -1 -1
1 3
4 1
13 10
1 1000
10 8
5 5
-1 1 -1 -1
-1 -1 1 -1
-1 -1 -1 10
-1 -1 -1 -1
1 4
4 3
30 60
10 1000
12 5
20 1
-1 10 -1 31
10 -1 10 -1
-1 -1 -1 10
15 6 -1 -1
2 4
3 1
3 2

样例输出 1

Case #1: 0.583333333
Case #2: 1.2
Case #3: 0.51 8.01 8.0

说明

注意，最后一个样例用例不会出现在小数据集中。

在 Case #1 中有两种选择：全程使用城市 1 的马，或者在城市 2 换马。两匹马的耐力都足够，所以两种选择都可行。由于城市 2 的马更快，换马更好，总时间为 $1/3 + 1/4$。

在 Case #2 中，有两个中间城市可以换马。然而，如果你在城市 2 换马，你的新马虽然速度极快，但耐力不足，所以你被迫在城市 3 再次换马。如果你保留原来的马，你将可以选择在城市 3 换马（或不换）。因此，三种选择及其总时间为： 1. 在城市 2 和 3 都换马 ($1/10 + 1/1000 + 10/8 = 1.351$)。 2. 只在城市 3 换马 ($2/10 + 10/8 = 1.45$)。 3. 从不换马 ($12/10 = 1.2$)。

在 Case #3 中，每次投递都有很多选择。第一次投递（城市 2 到城市 4）的最优方案是先以 $10/1000$ 的时间到达城市 1，换马，然后依次前往城市 2、3 和 4，使用来自城市 1 的马，这需要 $(10 + 10 + 10) / 60$ 的时间。

对于第二次投递（城市 3 到城市 2），你别无选择，只能先去城市 4，这需要 $10/5$ 的时间。你相对较快的马没有足够的耐力去其他任何地方，所以你需要换成城市 4 的马。你可以用它以 15 的时间直接到达城市 1，但这比骑它以 6 的时间到达城市 2，然后使用城市 2 速度极快的马以额外 $10/1000$ 的时间到达城市 1 要慢。

在 Case #3 的第三次投递（城市 3 到城市 1）中，最优方案是使用前一次投递的前两个步骤，总时间为 $10/5 + 6 = 8$。