Wormholes

A friend of yours has just built a spaceship and wants to explore space with it. On his first voyages he discovered that the universe is full of wormholes. A wormhole transports you instantly from its entry point to its exit point, and it can also shift you to a moment in the past or in the future.

Having mapped every wormhole together with its entry and exit points, you and your friend decide to fly to a distant destination and want to arrive as early as possible. Given your departure point, your destination, and all of the wormholes, determine the earliest time at which you can reach the destination.

The first line contains an integer $c$ ($1 \le c \le 200$), the number of test cases. Each test case is given as follows.

• The first line contains two coordinate triples $x_0\ y_0\ z_0$ and $x_1\ y_1\ z_1$: the departure point and the destination.
• The next line contains an integer $n$ ($0 \le n \le 50$), the number of wormholes.
• Each of the next $n$ lines describes one wormhole with two coordinate triples $x_s\ y_s\ z_s$ (entry) and $x_e\ y_e\ z_e$ (exit), followed by two integers $t$ and $d$ ($-1000000 \le t, d \le 1000000$): the creation time $t$ of the wormhole and the time shift $d$ applied when travelling through it.

All coordinates are integers with absolute value at most $10000$, and no two of the listed points coincide.

Time starts at $0$. The spaceship travels at speed $1$, and the distance between two points is their Euclidean distance rounded up to the nearest integer, that is $\lceil \sqrt{(\Delta x)^2 + (\Delta y)^2 + (\Delta z)^2} \rceil$. Passing through a wormhole is instantaneous: you may enter wormhole $i$ only at a time $T \ge t_i$ (you may wait before entering), and doing so places you at its exit point at time $T + d_i$.

For each test case, print a single line containing one integer: the earliest time at which you can arrive at your destination. This time may be negative.