Internet Problem Solving Contest

• Easy input data set – B1
• Hard input data set – B2

The Manhattan in the New York City has really a nice topology. So nice, it is often idealized to a rectangular grid. If you want to go from corner A = (A_x,A_y) to corner B = (B_x,B_y), the shortest way has length |A_x − B_x| + |A_y − B_y|. Or so they told you in school.

The truth is, the correct definition of a Manhattan metric has to involve the Broadway – a road that leads across the neatly aligned system of streets and avenues. In this problem we finally correct this horrible mistake made by the mathematical community.

Problem specification

Given the two corners A = (A_x,A_y),B = (B_x,B_y) and three rational numbers P, Q, R that describe the Broadway, your task is to find the length of the shortest path between points A and B.

The road network consists of the following roads:

• For each integer Z, there is an avenue described by the equation x = Z.
• For each integer Z, there is a street described by the equation y = Z.
• The Broadway is described by the equation Px + Qy = R.

When moving from A to B, we can only move along the roads and change roads at intersections.

Input specification

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of one line containing seven numbers:
four integers A_x,A_y,B_x,B_y specifying the points A = (A_x,A_y) and B = (B_x,B_y),
and three rational numbers P,Q,R specifying the Broadway as explained above.

Output specification

For each test case output a single line containing the length of the shortest path from A to B. Output a sufficient number of decimal places. Your output will be judged as correct if it has an absolute or relative error at most 10⁻⁹.

Example