Military Recruit

Tom is a recruit for an elite army unit. As the final part of his exams, he will be dropped into unknown terrain and must march to a designated exit point while carrying all of his heavy gear.

Because he is a little nervous, Tom has studied satellite images of the training area. He has identified every possible entry and exit site, together with the possible connections between sites and their estimated lengths. Because of differences in terrain height these connections are one-directional: the length from one site to another need not equal the length in the opposite direction, so the length from site $i$ to $j$ may differ from the length from $j$ to $i$.

Tom does not know in advance which site will be his start and which will be his exit. He realises that, no matter how hard he trains, he cannot possibly succeed in the worst case — the pair of sites that are farthest apart.

His instructors always choose two distinct sites as the entry and exit, and Tom assumes that every ordered pair of distinct $(\text{entry}, \text{exit})$ sites is equally likely. For a given pair, the distance he must march is the length of the shortest path from the entry site to the exit site.

Given the sites, the direct connections and their lengths, and Tom's desired success probability $p$, compute the minimum distance $D$ that he must be comfortable with so that he passes with probability at least $p\%$. In other words, $D$ is the smallest value for which the fraction of ordered $(\text{entry}, \text{exit})$ pairs whose shortest-path length is at most $D$ is at least $p / 100$.

The first line contains the number of scenarios.

Each scenario is given as follows. The first line contains an integer $p$ ($1 \le p \le 100$), Tom's minimum success probability as a percentage. The next line contains the number of sites $n$ ($2 \le n \le 100$). Each of the following $n$ lines contains $n$ integers separated by spaces: the $j$-th integer on the $i$-th line is the length of the direct connection from site $i$ to site $j$.

Every distance is a non-negative integer less than $1000$. The distance from a site to itself is always $0$. A value of $-1$ means there is no direct connection in that direction. You may assume that every site is reachable from every other site.

For each scenario, first print a line Scenario #i:, where $i$ is the scenario number starting at $1$. On the next line, print the minimum distance $D$ that Tom must be prepared for. Separate consecutive scenarios with a single blank line.