말 정속 주행

애니는 스트레스가 심한 버스 기사다. 카리브해 크루즈 여행으로 쉬어 보려 했지만 그것도 스트레스여서, 최근에는 승마를 시작했다.

오늘 애니는 서쪽에서 동쪽으로 뻗은 좁고 긴 일방통행 도로를 따라 말을 타고 동쪽으로 간다. 지금은 도로의 0킬로미터 지점에 있고, 목적지는 $D$킬로미터 지점이다. 킬로미터 표시는 서쪽에서 동쪽으로 커진다.

같은 도로를 동쪽으로 달리는 다른 말이 $N$마리 있다. 이 말은 모두 멈추지 않고 계속 달리며, 지금은 전부 애니의 말과 목적지 사이에 있다. $i$번째 말은 처음에 $K_i$킬로미터 지점에 있고 최대 속도 시속 $S_i$킬로미터로 달린다.

말은 아주 예의가 바르다. 말 $H_1$은 자기보다 앞에서 출발한 말 $H_2$를 추월하지 않는다. 두 마리 이상이 같은 위치에 얼마든지 오래 함께 있어도 되고, 말은 크기가 없는 점으로 본다. 애니의 말을 뺀 나머지는 모두 최대 속도로 달리되, $H_1$이 앞의 더 느린 말 $H_2$를 따라잡으면 속도를 $H_2$에 맞춰 낮춘다.

애니의 말에는 최대 속도가 없어서, 다른 말을 추월하지만 않는다면 애니가 정하는 어떤 속도로도 달린다. 애니는 편안하게 가려고 지금 위치에서 목적지까지 전 구간을 하나의 일정한 속도로 달리려 하며, 그 속도로 달려도 다른 말을 추월하지 않아야 한다. 이런 속도의 최댓값을 구하여라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $D$와 $N$이 주어진다. $D$는 모든 말의 목적지 위치(킬로미터)이고, $N$은 도로 위에 있는 다른 말의 수다. 다음 $N$개 줄 중 $i$번째 줄에는 두 정수 $K_i$와 $S_i$가 주어진다. 각각 $i$번째 말의 처음 위치(킬로미터)와 최대 속도(시속 킬로미터)다.

제한

• $1 \le T \le 100$
• 모든 $i$에 대해 $0 < K_i < D \le 10^9$
• $i \ne j$이면 $K_i \ne K_j$ (두 말이 같은 위치에서 출발하지 않는다)
• $1 \le S_i \le 10000$
• $1 \le N \le 1000$

각 테스트 케이스마다 Case #x: p/q 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, p/q는 애니가 다른 말을 추월하지 않고 유지할 수 있는 최대 속도(시속 킬로미터)를 기약분수로 나타낸 것이다.

답은 언제나 유리수다. $\gcd(p, q) = 1$, $q \ge 1$인 정수 $p$와 $q$를 써야 한다. 답이 정수 $n$이어도 분모를 생략하지 않고 n/1로 출력한다.

예제의 첫 번째 테스트 케이스에는 아주 느린 말 한 마리만 있다. 이 말은 25시간 뒤에 목적지에 닿는다. 애니가 시속 101킬로미터보다 빠르게 달리면 목적지에 닿기 전에 그 말을 추월하므로, 답은 101/1이다.

두 번째 테스트 케이스에는 말이 두 마리 있다. 빠른 말이 2시간 뒤 240킬로미터 지점에서 느린 말을 따라잡고, 그때부터 두 마리가 느린 말의 속도로 1시간을 더 달려 300킬로미터 지점의 목적지에 도착한다. 애니가 추월 없이 고를 수 있는 최대 속도는 시속 100킬로미터이고, 답은 100/1이다.