Goose, Goose, Ducks?

The first international Geese conference just wrapped up. It should have been a happy occasion, but it ended on a bittersweet note. The organizers found a paper with detailed plans for a duck infiltration, and they are now trying to identify the infiltrating group among the attendees.

The document contained a list of $M$ triples of integers $(X_i, Y_i, C_i)$. Each triple means the ducks would meet exactly $C_i$ seconds after the start of the conference at point $(X_i, Y_i)$, which is $X_i$ meters east and $Y_i$ meters north of the center of the conference floor. A goose may or may not have been at that point at that time. Every duck certainly was.

Ducks and geese both walk at a maximum speed of 1 meter per second. An attendee at point $(x, y)$ at time $t$ can reach $(x+\Delta_x, y+\Delta_y)$ by time $t+\Delta_t$ as long as $\Delta_x^2+\Delta_y^2 \le \Delta_t^2$. Each attendee's position at time 0 can be any point, independently of the other attendees.

After the discovery, the group held a questioning session to identify the ducks. Attendees made statements one at a time. The $j$-th statement was made by attendee $A_j$, who claimed that both $A_j$ and attendee $B_j$ were at point $(U_j, V_j)$ exactly $D_j$ seconds after the start of the conference. A point in a statement may or may not be a point where a duck meeting happened.

Statements from geese are always true, but ducks may lie. Ducks know which attendees are ducks and which are geese. To avoid getting caught, ducks only make statements that are consistent with all earlier statements made by geese. Statements from geese are consistent with all ducks being at all duck meetings.

A hypothesis $H$ is a partition of all attendees into a set of ducks ($H$-ducks) and a set of geese ($H$-geese). $H$ is consistent with a set of statements $S$ if every attendee has a path moving at most 1 meter per second such that:

• all $H$-ducks are at all duck meetings, and
• for each statement in $S$ claiming that $A$ saw $B$ at point $P$ at time $T$, the paths of both $A$ and $B$ pass through $P$ at time $T$.

A hypothesis $H$ is feasible under a set of statements $S$ if:

• $H$-ducks is not empty, so at least one duck exists,
• the statements in $S$ made by $H$-geese are consistent with $H$, so geese tell the truth, and
• for each statement $s \in S$ made by an $H$-duck, let $P$ be the set of statements made by $H$-geese before $s$. Then there is some hypothesis $H'$, which may or may not equal $H$, such that $\{s\} \cup P$ is consistent with $H'$. So ducks do not contradict earlier goose statements.

The hypothesis in which every attendee is a duck is always feasible.

Find the minimum size of $H$-ducks over all feasible hypotheses $H$.

The first line contains the number of test cases $T$. Each test case starts with a line containing three integers $N$, $M$, and $S$, the numbers of attendees, duck meetings, and statements.

The next $M$ lines each contain three integers $X_i$, $Y_i$, and $C_i$. This means there was a duck meeting at point $(X_i, Y_i)$, exactly $C_i$ seconds after the start of the conference.

The last $S$ lines of the test case each describe a statement with five integers $A_j$, $B_j$, $U_j$, $V_j$, and $D_j$. Attendee $A_j$ stated that $A_j$ and $B_j$ were both at point $(U_j, V_j)$ exactly $D_j$ seconds after the start of the conference. Statements are given in the order they were issued.

For each test case, output one line containing Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of ducks that might have infiltrated the conference.

• $1 \le T \le 50$.
• $-10^9 \le X_i \le 10^9$ for all $i$.
• $-10^9 \le Y_i \le 10^9$ for all $i$.
• $1 \le C_i \le 10^9$ for all $i$.
• $C_i < C_{i+1}$ for all $i$.
• $(X_i - X_{i+1})^2 + (Y_i - Y_{i+1})^2 \le (C_i - C_{i+1})^2$ for all $i$.
• $1 \le A_j \le N$ for all $j$.
• $1 \le B_j \le N$ for all $j$.
• $A_j \ne B_j$ for all $j$.
• $-10^9 \le U_j \le 10^9$ for all $j$.
• $-10^9 \le V_j \le 10^9$ for all $j$.
• $1 \le D_j \le 10^9$ for all $j$.
• $(A_j, B_j, U_j, V_j, D_j) \ne (A_k, B_k, U_k, V_k, D_k)$ for all $j \ne k$.

In Sample Case #1, attendee 1 being the only duck is a feasible hypothesis.

In Sample Case #2, attendees 2 and 4 being the only ducks is a feasible hypothesis. There is at least one duck, so all attendees being geese is not feasible.