Annie 是一名压力很大的公交车司机。她曾尝试去加勒比海游轮旅行来放松心情，但那次旅行也让她感到压力重重，所以她最近开始学习骑马。

今天，Annie 正在一条从西向东延伸的狭长单行道上骑马向东行驶。她目前位于道路的 0 公里处，目的地位于 $D$ 公里处；道路上的公里数从西向东编号。

路上还有 $N$ 匹马也在向东行驶；它们都会一直走下去，且目前都位于 Annie 的马和目的地之间。其中第 $i$ 匹马的初始位置为 $K_i$ 公里，最大速度为 $S_i$ 公里/小时。

马是非常有礼貌的，如果一匹马 $H_1$ 起始位置在另一匹马 $H_2$ 的后方，那么 $H_1$ 就不会超过（跑到 $H_2$ 前面）$H_2$。（两匹或多匹马可以在任何时间内处于同一位置；你可以将马视为质点。）除了 Annie 的马以外，其他马都以它们的最大速度行驶，但每当马 $H_1$ 追上另一匹较慢的马 $H_2$ 时，$H_1$ 会降低速度以匹配 $H_2$ 的速度。

另一方面，Annie 的马没有最大速度限制，只要不超越其他马，Annie 可以选择任何速度。为了确保她和她的马能平稳骑行，Annie 希望为她的马在整个行程中（从当前位置到目的地）选择一个恒定的“巡航控制”速度，使得她的马不会超过任何其他马。她能选择的最大速度是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以两个整数 $D$ 和 $N$ 开始：所有马的目的地位置（以公里为单位）以及路上其他马的数量。接下来有 $N$ 行，第 $i$ 行包含两个整数 $K_i$ 和 $S_i$：路上第 $i$ 匹马的初始位置（以公里为单位）和最大速度（以公里/小时为单位）。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Annie 在不与其他马发生碰撞的情况下可以使用的最大恒定速度（以公里/小时为单位）。如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则被视为正确。

数据范围

$1 \le T \le 100$ $0 < K_i < D \le 10^9$，对于所有 $i$ $K_i \neq K_j$，对于所有 $i \neq j$（没有两匹马从同一位置出发） $1 \le S_i \le 10000$

样例

样例输入 1

3
2525 1
2400 5
300 2
120 60
60 90
100 2
80 100
70 10

样例输出 1

Case #1: 101.000000
Case #2: 100.000000
Case #3: 33.333333

说明

在样例 1 中，路上有一匹其他（非常慢的！）马；它将在 25 小时后到达 Annie 的目的地。任何超过 101 公里/小时的速度都会导致 Annie 在到达目的地之前超过这匹马。

在样例 2 中，路上有两匹其他马。较快的马将在 2 小时后在 240 公里处追上较慢的马。此后两匹马将以较慢马的速度再行驶 1 小时，直到它们到达 Annie 位于 300 公里处的目的地。Annie 在不超越其他马的情况下可以选择的最大速度是 100 公里/小时。