신병 행군

톰은 정예 부대의 신병입니다. 최종 시험의 마지막 단계로, 톰은 낯선 지형에 투입되어 무거운 군장을 모두 짊어진 채 지정된 도착 지점까지 행군해야 합니다.

조금 긴장한 톰은 훈련장의 위성 사진을 미리 분석했습니다. 그는 가능한 모든 출발 지점과 도착 지점, 그리고 지점들 사이의 연결과 그 예상 길이를 모두 파악했습니다. 지형의 고도 차이 때문에 이 연결은 한 방향으로만 성립합니다. 즉, 지점 $i$에서 $j$로 가는 길이와 $j$에서 $i$로 가는 길이가 서로 다를 수 있습니다.

톰은 어느 지점에서 출발해 어느 지점에 도착할지 미리 알 수 없습니다. 아무리 열심히 훈련해도 서로 가장 멀리 떨어진 두 지점이 걸리는 최악의 경우에는 성공할 수 없다는 것을 깨닫습니다.

교관은 항상 서로 다른 두 지점을 출발지와 도착지로 고르며, 톰은 서로 다른 $(\text{출발지}, \text{도착지})$ 순서쌍이 모두 같은 확률로 뽑힌다고 가정합니다. 어떤 쌍에 대해 톰이 행군해야 하는 거리는 출발지에서 도착지까지의 최단 경로 길이입니다.

지점들, 지점 사이의 직접 연결과 그 길이, 그리고 톰이 원하는 성공 확률 $p$가 주어질 때, 톰이 적어도 $p\%$의 확률로 시험을 통과하기 위해 대비해야 하는 최소 거리 $D$를 구하세요. 다시 말해, 최단 경로 길이가 $D$ 이하인 $(\text{출발지}, \text{도착지})$ 순서쌍의 비율이 $p / 100$ 이상이 되는 가장 작은 $D$를 구하면 됩니다.

첫 번째 줄에 시나리오의 개수가 주어집니다.

각 시나리오는 다음과 같이 주어집니다. 첫 줄에는 톰의 최소 성공 확률(백분율) $p$ ($1 \le p \le 100$)가 주어집니다. 다음 줄에는 지점의 개수 $n$ ($2 \le n \le 100$)이 주어집니다. 이어지는 $n$개의 줄에는 각각 $n$개의 정수가 공백으로 구분되어 주어지며, $i$번째 줄의 $j$번째 정수는 지점 $i$에서 지점 $j$로 가는 직접 연결의 길이입니다.

모든 거리는 $1000$ 미만의 음이 아닌 정수입니다. 한 지점에서 자기 자신까지의 거리는 항상 $0$입니다. 값이 $-1$이면 해당 방향으로의 직접 연결이 없다는 뜻입니다. 모든 지점은 다른 어떤 지점에서도 도달할 수 있다고 가정해도 됩니다.

각 시나리오마다 먼저 Scenario #i:를 한 줄에 출력합니다. 여기서 $i$는 $1$부터 시작하는 시나리오 번호입니다. 다음 줄에는 톰이 대비해야 하는 최소 거리 $D$를 출력합니다. 연속한 시나리오 사이에는 빈 줄을 하나 넣어 구분합니다.