The first line of input contains an integer c (1 <= c <= 200), the number of test cases. Each test case starts with a line containing two coordinate triples x0, y0, z0 and x1, y1, z1, the space coordinates of your departure point and destination. The next line contains an integer n (0 <= n <= 50), the number of wormholes. Then follow n lines, one for each wormhole, with two coordinate triples xs, ys, zs and xe, ye, ze, the space coordinates of the wormhole entry and exit points, respectively, followed by two integers t, d ( -1 000 000 <= t, d <= 1 000 000), the creation time t of the wormhole and the time shift d when traveling through the wormhole.
All coordinates are integers with absolute values smaller than or equal to 10 000 and no two points are the same.
Note that, initially, the time is zero, and that tunneling through a wormhole happens instantly. For simplicity, the distance between two points is deffned as their Euclidean distance (the square root of the sum of the squares of coordinate differences) rounded up to the nearest integer. Your friend's spaceship travels at speed 1.