Government of the cities Los Santos, San Fierro and Las Venturas, situated within the state San Andreas, decided to build a farm. Citizens of Los Santos claimed that they will travel to the farm by subway, citizens of San Fierro will travel by car and citizens of Las Venturas will travel by train.

You know the amount of money required to build one kilometer of subway line, one kilometer of highway and one kilometer of railroad. Help the government choose a place for the farm that would minimize the total amount of money required to build roads of all three types.

The first line contains the number of test cases t (1 ≤ t ≤ 10⁴). Each test case consists of four lines. The first three lines contain the coordinates of Los Santos, San Fierro and Las Venturas, respectively. All coordinates are integers and don't exceed 1000 in their absolute value. The fourth line contains the costs of building a kilometer of subway line, highway and railroad. These costs are positive integers, not exceeding 1000.

For each test case output in a single line the minimal amount of money required to build all roads from the cities to the farm, with absolute or relative error not exceeding 10⁻⁹.