Commute War (Small)

Yeongsu starts his first job next week. Public transport in Seoul is dense, but every vehicle now has to pass a police checkpoint. To avoid being late on his first day, Yeongsu collected the timetable and the expected delay of every ride on the way to the office. Find the expected time at which he reaches the office.

One ride behaves like this.

• It leaves its origin stop at minute $S$ of every hour, that is at times $S$, $S+60$, $S+120$, and so on. If Yeongsu is at the origin stop at time $t$, he boards the earliest departure at time $t$ or later. A departure exactly at time $t$ counts.
• Reaching the destination stop takes $R$ minutes.
• The police check the vehicle during the trip. The check itself costs no time, but with probability $P$ percent something is wrong and the vehicle is held for $D$ minutes. After those $D$ minutes the check runs again and can hold the vehicle again with the same probability. The check repeats until it passes. If the check finds a problem $k$ times, the trip takes $R + D \times k$ minutes.
• Once aboard, Yeongsu cannot get off before the destination stop.

A ride with $P = 100$ never passes the check, so it never reaches its destination stop.

Yeongsu leaves home at time $0$, and at every stop he takes the ride that minimizes the expected arrival time.

The first line has the number of test cases $T$.

The first line of each test case has four integers $N$, $M$, $H$, $O$ separated by spaces. $N$ is the number of stops, $M$ is the number of rides, $H$ is the stop where his home is, and $O$ is the stop where the office is.

Each of the next $M$ lines has six integers $A_i$, $B_i$, $S_i$, $R_i$, $D_i$, $P_i$ for one ride. $A_i$ is the origin stop, $B_i$ is the destination stop, $S_i$ is the minute of each hour at which the ride departs, $R_i$ is the travel time, $D_i$ is the length of one delay, and $P_i$ is the probability that a check finds a problem. $P_i$ is a percentage.

Constraints

• $1 \le T \le 100$
• $2 \le N \le 100$
• $0 \le M \le N - 1$
• $0 \le H, O, A_i, B_i < N$
• $0 \le S_i \le 59$
• $1 \le R_i \le 100$
• $1 \le D_i \le 100$
• $0 \le P_i \le 100$
• $B_i = A_i + 1$ for every $i$
• $A_i \ne A_j$ or $B_i \ne B_j$ for every pair $i < j$, so at most one ride leaves each stop

For each test case print one line in the form Case #x: y, where $x$ is the test case number starting at $1$.

If Yeongsu can reach the office, $y$ is the expected arrival time rounded to seven digits after the decimal point, with all seven digits printed, so an expectation that is exactly an integer still carries seven zeros after the point. If he cannot reach the office, print -1 in place of $y$, with no decimal point. When $H = O$ the expectation is $0$, so print 0.0000000.