Es un hecho matemático famoso que si colocas un mapa de un parque completamente dentro del parque, entonces existe un punto en el mapa que coincide con el punto que representa.
Mio disfruta mucho este hecho, así que coloca un mapa de su parque favorito completamente dentro del parque. El parque $P$ puede representarse mediante un rectángulo. Un mapa del parque es simplemente una versión más pequeña (o igual) del parque impresa en papel. El mapa es similar al rectángulo original. Cada punto en el mapa corresponde a un punto en el parque mediante la transformación de semejanza.
Podemos definir un mapa formalmente: un mapa es un rectángulo $M$ (de tamaño menor o igual) junto con un número real positivo $r$ y una función biyectiva $f : M \to P$ que satisface:
- Para cada par de puntos diferentes $a, b \in M$, $|f(a) - f(b)| / |a - b| = r$.
$|x - y|$ representa la distancia euclidiana entre los puntos $x$ e $y$.
Como en muchos juegos, Mio puede teletransportarse usando el mapa. Precisamente, cuando Mio está en algún punto $x$ del mapa (incluyendo el borde), puede teletransportarse al punto correspondiente $f(x)$ en el parque. También puede elegir no teletransportarse. Lo inverso también es cierto. Cuando está en el punto $y$ en el parque (incluyendo el borde), puede teletransportarse al punto $f^{-1}(y)$ en el mapa que representa su ubicación actual. Y también puede elegir no teletransportarse.
Mio puede teletransportarse como máximo $n$ veces (y al menos 0). Cada teletransporte toma $k$ segundos. Mio también puede caminar a pie a una velocidad de 1 unidad por segundo.
Dados dos puntos $s$ y $t$, encuentre el tiempo mínimo que necesita Mio para llegar a $t$ desde $s$.
Cada teletransporte puede ser en cualquier dirección (del mapa al parque, o del parque al mapa). El mapa puede estar colocado boca abajo. Dado que el mapa está dentro del parque, es posible que Mio esté en el mapa y en el parque simultáneamente. En este caso, puede teletransportarse en cualquier dirección.
Por ejemplo, en la siguiente figura, el parque es $ABCD$ y el mapa es $A'B'C'D'$. Cuando Mio está dentro del mapa, está en el mapa y en el parque simultáneamente. Cuando está en el punto $D'$, puede teletransportarse del mapa al parque (llegando a $D$), y del parque al mapa (llegando a $D'$).
El parque es ABCD y el mapa es A'B'C'D'.
Entrada
La primera línea contiene un único entero $T$ ($1 \le T \le 100$) que denota el número de casos de prueba.
Para cada caso de prueba, la primera línea contiene las 4 esquinas del rectángulo que representa el parque. Las esquinas se dan en orden horario o antihorario. Se garantiza que las 4 esquinas son distintas.
La segunda línea contiene las 4 esquinas del rectángulo que representa el mapa. La $i$-ésima esquina del mapa corresponde a la $i$-ésima esquina del parque para todo $1 \le i \le 4$. Tenga en cuenta que puede determinar si el mapa está colocado boca abajo o no por el orden de las esquinas. Las esquinas se dan en orden horario o antihorario. Se garantiza que el mapa está dentro del parque. (El borde del mapa puede intersectar el borde del parque en 1 o más puntos). Se garantiza que el mapa es válido, es decir, existe un número real positivo y una función biyectiva del mapa al parque que satisface la definición anterior.
La tercera línea contiene dos puntos $s$ y $t$. Se garantiza que $s$ y $t$ están dentro (o en el borde) del parque.
La cuarta línea contiene dos enteros $k, n$ ($0 \le k \le 2 \times 10^6$, $0 \le n \le 100$), el tiempo que requiere cada teletransporte y el número máximo de teletransportes.
Cada punto en la entrada está representado por un par de enteros cuyos valores absolutos no superan $2 \times 10^6$. Los enteros están separados por espacios simples.
Salida
Para cada caso de prueba, imprima un número que represente la respuesta en una línea. Su respuesta se considera correcta si su error absoluto o relativo no excede $10^{-9}$.
Ejemplos
Entrada 1
2 0 0 0 2 4 2 4 0 0 0 0 1 2 1 2 0 2 1 4 2 1 1 0 0 0 3 6 3 6 0 0 1 1 0 3 2 2 3 0 0 4 2 0 3
Salida 1
1.0000000000 1.2272623352