這是一個著名的數學事實：如果你將公園的地圖完全放置在公園內部，那麼地圖上必然存在一個點，與它所代表的公園內的點重合。

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'$）。

輸入格式

第一行包含一個整數 $T$ ($1 \le T \le 100$)，表示測試案例的數量。

對於每個測試案例，第一行包含代表公園的矩形的 4 個頂點。頂點以順時針或逆時針順序給出。保證 4 個頂點各不相同。

第二行包含代表地圖的矩形的 4 個頂點。地圖的第 $i$ 個頂點對應公園的第 $i$ 個頂點，對於所有 $1 \le i \le 4$。注意，你可以透過頂點的順序判斷地圖是否被倒置。頂點以順時針或逆時針順序給出。保證地圖位於公園內部。（地圖的邊界可能與公園的邊界在 1 個或多個點上相交。）保證地圖是有效的，即存在一個正實數和一個從地圖到公園的雙射函數，滿足上述定義。

第三行包含兩個點 $s$ 和 $t$。保證 $s$ 和 $t$ 位於公園內部（或邊界上）。

第四行包含兩個整數 $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 3 6 3 6 0
0 1 1 0 3 2 2 3
0 0 4 2
0 3

輸出格式 1

1.0000000000
1.2272623352