C'est un fait mathématique célèbre que si vous déposez une carte d'un parc complètement à l'intérieur du parc, alors il existe un point sur la carte qui se superpose au point qu'il représente.

Mio aime beaucoup ce fait, alors elle dépose une carte de son parc préféré complètement à l'intérieur du parc. Le parc $P$ peut être représenté par un rectangle. Une carte du parc est simplement une version plus petite (ou égale) du parc imprimée sur papier. La carte est semblable au rectangle original. Chaque point sur la carte correspond à un point dans le parc par une transformation de similitude.

Nous pouvons définir une carte formellement : une carte est un rectangle $M$ (de taille plus petite ou égale) accompagné d'un nombre réel positif $r$ et d'une fonction bijective $f : M \to P$ satisfaisant :

• Pour toute paire de points différents $a, b \in M$, $|f(a) - f(b)|/|a - b| = r$.

$|x - y|$ représente la distance euclidienne entre les points $x$ et $y$.

Comme dans beaucoup de jeux, Mio peut se téléporter en utilisant la carte. Précisément, lorsque Mio est à un point $x$ sur la carte (y compris la frontière), elle peut se téléporter au point correspondant $f(x)$ dans le parc. Elle peut également choisir de ne pas se téléporter. L'inverse est également vrai. Lorsqu'elle est au point $y$ dans le parc (y compris la frontière), elle peut se téléporter au point $f^{-1}(y)$ sur la carte représentant son emplacement actuel. Et elle peut également choisir de ne pas se téléporter.

Mio peut se téléporter au plus $n$ fois (et au moins 0 fois). Chaque téléportation prend $k$ secondes. Mio peut également marcher à pied à une vitesse de 1 unité par seconde.

Étant donné deux points $s$ et $t$, trouvez le temps minimum dont Mio a besoin pour atteindre $t$ depuis $s$.

Chaque téléportation peut se faire dans n'importe quelle direction (de la carte vers le parc, ou du parc vers la carte). La carte peut être placée à l'envers. Puisque la carte est à l'intérieur du parc, il est possible que Mio soit sur la carte et dans le parc simultanément. Dans ce cas, elle peut se téléporter dans l'une ou l'autre direction.

Par exemple, dans la figure suivante, le parc est $ABCD$ et la carte est $A'B'C'D'$. Lorsque Mio est à l'intérieur de la carte, elle est sur la carte et dans le parc simultanément. Lorsqu'elle est au point $D'$, elle peut se téléporter de la carte vers le parc (atteignant $D$), et du parc vers la carte (atteignant $D$).

Entrée

La première ligne contient un entier unique $T$ ($1 \le T \le 100$) indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient les 4 coins du rectangle représentant le parc. Les coins sont donnés dans l'ordre horaire ou anti-horaire. Il est garanti que les 4 coins sont distincts.

La deuxième ligne contient les 4 coins du rectangle représentant la carte. Le $i$-ième coin de la carte correspond au $i$-ième coin du parc pour tout $1 \le i \le 4$. Notez que vous pouvez déterminer si la carte est placée à l'envers ou non par l'ordre des coins. Les coins sont donnés dans l'ordre horaire ou anti-horaire. Il est garanti que la carte est à l'intérieur du parc. (La frontière de la carte peut intersecter la frontière du parc en 1 point ou plus.) Il est garanti que la carte est valide, c'est-à-dire qu'il existe un nombre réel positif et une fonction bijective de la carte vers le parc satisfaisant la définition ci-dessus.

La troisième ligne contient deux points $s$ et $t$. Il est garanti que $s$ et $t$ sont à l'intérieur (ou sur la frontière) du parc.

La quatrième ligne contient deux entiers $k, n$ ($0 \le k \le 2 \times 10^6$, $0 \le n \le 100$), le temps nécessaire pour chaque téléportation et le nombre maximum de téléportations.

Chaque point dans l'entrée est représenté par une paire d'entiers dont les valeurs absolues ne dépassent pas $2 \times 10^6$. Les entiers sont séparés par des espaces simples.

Sortie

Pour chaque cas de test, affichez un nombre représentant la réponse sur une ligne. Votre réponse est considérée comme correcte si son erreur absolue ou relative n'excède pas $10^{-9}$.

Exemples

Entrée 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

Sortie 1

1.0000000000
1.2272623352