공원 지도를 공원 내부에 완전히 펼쳐 놓으면, 지도상의 한 점이 그 점이 나타내는 공원의 실제 지점과 일치하게 된다는 유명한 수학적 사실이 있습니다.

Mio는 이 사실을 매우 좋아하여, 자신이 가장 좋아하는 공원의 지도를 공원 내부에 완전히 펼쳐 놓았습니다. 공원 $P$는 직사각형으로 나타낼 수 있습니다. 공원의 지도는 종이에 인쇄된 공원의 더 작거나 같은 버전입니다. 지도는 원래의 직사각형과 닮음 관계에 있습니다. 지도상의 각 점은 닮음 변환을 통해 공원 내의 한 점에 대응됩니다.

지도를 형식적으로 정의하면 다음과 같습니다. 지도는 더 작거나 같은 크기의 직사각형 $M$과 양의 실수 $r$, 그리고 다음을 만족하는 전단사 함수 $f : M \to P$로 구성됩니다.

• 서로 다른 모든 두 점 $a, b \in M$에 대하여, $|f(a) - f(b)| / |a - b| = r$입니다.

$|x - y|$는 점 $x$와 $y$ 사이의 유클리드 거리를 나타냅니다.

많은 게임에서와 마찬가지로, Mio는 지도를 사용하여 순간이동을 할 수 있습니다. 구체적으로, Mio가 지도상의 어떤 점 $x$에 있을 때(경계 포함), 그녀는 공원 내의 대응되는 점 $f(x)$로 순간이동할 수 있습니다. 순간이동을 하지 않을 수도 있습니다. 그 반대도 성립합니다. 그녀가 공원 내의 점 $y$에 있을 때(경계 포함), 그녀는 현재 위치를 나타내는 지도상의 점 $f^{-1}(y)$로 순간이동할 수 있습니다. 마찬가지로 순간이동을 하지 않을 수도 있습니다.

Mio는 최대 $n$번(최소 0번) 순간이동할 수 있습니다. 각 순간이동에는 $k$초가 걸립니다. Mio는 또한 초당 1단위의 속도로 걸어 다닐 수 있습니다.

두 점 $s$와 $t$가 주어졌을 때, Mio가 $s$에서 $t$까지 도달하는 데 필요한 최소 시간을 구하세요.

각 순간이동은 어느 방향으로든 가능합니다(지도에서 공원으로, 또는 공원에서 지도로). 지도는 뒤집혀 배치될 수도 있습니다. 지도가 공원 내부에 있으므로, Mio가 지도 위에 있으면서 동시에 공원 내에 있을 수도 있습니다. 이 경우, 그녀는 어느 방향으로든 순간이동할 수 있습니다.

예를 들어, 다음 그림에서 공원은 $ABCD$이고 지도는 $A'B'C'D'$입니다. Mio가 지도 내부에 있을 때, 그녀는 지도 위에 있으면서 동시에 공원 내에 있습니다. 그녀가 점 $D'$에 있을 때, 지도에서 공원으로 순간이동하여 $D$에 도달할 수 있고, 공원에서 지도로 순간이동하여 $D'$에 도달할 수 있습니다.

예를 들어, 공원은 ABCD이고 지도는 A'B'C'D'입니다. Mio가 지도 내부에 있을 때, 그녀는 지도 위에 있으면서 동시에 공원 내에 있습니다. 그녀가 점 D'에 있을 때, 지도에서 공원으로 순간이동하여 D에 도달할 수 있고, 공원에서 지도로 순간이동하여 D'에 도달할 수 있습니다.

입력

첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 100$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 공원을 나타내는 직사각형의 네 꼭짓점이 주어집니다. 꼭짓점은 시계 방향 또는 반시계 방향 순서로 주어집니다. 네 꼭짓점은 서로 다름이 보장됩니다.

두 번째 줄에는 지도를 나타내는 직사각형의 네 꼭짓점이 주어집니다. 지도의 $i$번째 꼭짓점은 공원의 $i$번째 꼭짓점에 대응됩니다 ($1 \le i \le 4$). 꼭짓점의 순서를 통해 지도가 뒤집혀 배치되었는지 여부를 파악할 수 있습니다. 꼭짓점은 시계 방향 또는 반시계 방향 순서로 주어집니다. 지도는 공원 내부에 있음이 보장됩니다. (지도의 경계는 공원의 경계와 한 점 이상에서 만날 수 있습니다.) 지도는 유효함이 보장됩니다. 즉, 위에서 정의한 조건을 만족하는 양의 실수와 지도에서 공원으로의 전단사 함수가 존재합니다.

세 번째 줄에는 두 점 $s$와 $t$가 주어집니다. $s$와 $t$는 공원 내부(또는 경계 위)에 있음이 보장됩니다.

네 번째 줄에는 각 순간이동에 필요한 시간 $k$와 최대 순간이동 횟수 $n$을 나타내는 두 정수 $k, n$ ($0 \le k \le 2 \times 10^6, 0 \le n \le 100$)이 주어집니다.

입력의 각 점은 절댓값이 $2 \times 10^6$ 이하인 정수 쌍으로 표현됩니다. 정수들은 공백으로 구분됩니다.

출력

각 테스트 케이스마다 정답을 한 줄에 하나씩 출력하세요. 절댓값 또는 상대 오차가 $10^{-9}$ 이하이면 정답으로 간주됩니다.

예제

입력 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

출력 1

1.0000000000
1.2272623352