Правительства городов Лос-Сантос, Сан-Фиерро и Лас-Вентурас, расположенных в штате Сан-Андреас, решили построить общую ферму. Жители Лос-Сантоса заявили, что будут ездить на ферму только на метро, жители Сан-Фиерро — только на автомобиле, а жители Лас-Вентураса — только на электричке.

Известна сумма, которую необходимо потратить на строительство километра линии метро, километра автомагистрали и километра железнодорожных путей. Помогите выбрать место для фермы таким образом, чтобы потратить на строительство дорог всех типов как можно меньшую сумму.

В первой строке записано число t (1 ≤ t ≤ 10⁴) — количество тестов. Каждый тест состоит из четырёх строк. В первой строке записаны координаты Лос-Сантоса, во второй — Сан-Фиерро, а в третьей — Лас-Вентураса. Все координаты целые, даны в километрах и не превосходят по модулю 1000. В четвёртой строке записаны стоимости строительства километра линии метро, автомагистрали и железной дороги. Эти стоимости целые, положительные, и не превосходят 1000.

Для каждого теста выведите в отдельной строке минимальную сумму, которую придётся потратить на строительство дорог всех типов, с абсолютной или относительной погрешностью не более 10⁻⁹.