公園の地図を公園の内部に完全に広げると、地図上の点とそれが表す公園内の点が重なる場所が必ず存在するという有名な数学的事実があります。

Mioはこの事実をとても気に入っており、お気に入りの公園の地図を公園の内部に完全に広げました。公園 $P$ は長方形で表されます。公園の地図は、紙に印刷された公園の縮小版（または等倍版）です。地図は元の長方形と相似です。地図上の各点は、相似変換によって公園内の点に対応します。

地図を形式的に定義します。地図とは、長方形 $M$（サイズは公園以下）、正の実数 $r$、および以下の条件を満たす全単射関数 $f : M \to P$ の組です。

• 異なる任意の2点 $a, b \in M$ に対して、 $|f(a) - f(b)| / |a - b| = r$ が成り立つ。

$|x - y|$ は点 $x$ と点 $y$ の間のユークリッド距離を表します。

多くのゲームと同様に、Mioは地図を使ってテレポートすることができます。具体的には、Mioが地図上の点 $x$（境界を含む）にいるとき、公園内の対応する点 $f(x)$ にテレポートできます。テレポートしないことを選択することも可能です。逆もまた同様です。Mioが公園内の点 $y$（境界を含む）にいるとき、現在の場所を表す地図上の点 $f^{-1}(y)$ にテレポートできます。テレポートしないことを選択することも可能です。

Mioは最大 $n$ 回（最低0回）テレポートできます。各テレポートには $k$ 秒かかります。また、Mioは秒速1単位の速さで歩くこともできます。

2点 $s$ と $t$ が与えられたとき、Mioが $s$ から $t$ に到達するために必要な最小時間を求めてください。

各テレポートはどの方向（地図から公園へ、または公園から地図へ）でも可能です。地図は上下逆さまに置かれている可能性があります。地図は公園の内部にあるため、Mioが地図上かつ公園内に同時に存在することがあります。この場合、どちらの方向にでもテレポートできます。

例えば、以下の図において、公園は $ABCD$ であり、地図は $A'B'C'D'$ です。Mioが地図の内部にいるとき、彼女は地図上かつ公園内に同時に存在しています。彼女が点 $D'$ にいるとき、地図から公園へテレポートして $D$ に到達したり、公園から地図へテレポートして $D$ に到達したりすることができます。

公園は ABCD であり、地図は A'B'C'D' です。

入力

入力の最初の行には、テストケースの数を示す整数 $T$ ($1 \le T \le 100$) が含まれます。

各テストケースの最初の行には、公園を表す長方形の4つの頂点が含まれます。頂点は時計回りまたは反時計回りの順序で与えられます。4つの頂点は互いに異なることが保証されています。

2行目には、地図を表す長方形の4つの頂点が含まれます。地図の $i$ 番目の頂点は、公園の $i$ 番目の頂点に対応します ($1 \le i \le 4$)。頂点の順序から地図が上下逆さまに置かれているかどうかを判断できることに注意してください。頂点は時計回りまたは反時計回りの順序で与えられます。地図は公園の内部にあることが保証されています。（地図の境界は、公園の境界と1点以上で交差する場合があります。）地図は有効であること、すなわち、上記の定義を満たす正の実数と地図から公園への全単射関数が存在することが保証されています。

3行目には2点 $s$ と $t$ が含まれます。$s$ と $t$ は公園の内部（または境界上）にあることが保証されています。

4行目には、各テレポートに必要な時間 $k$ と最大テレポート回数 $n$ を表す2つの整数 $k, n$ ($0 \le k \le 2 \times 10^6, 0 \le n \le 100$) が含まれます。

入力内の各点は、絶対値が $2 \times 10^6$ 以下の整数のペアで表されます。整数はスペースで区切られています。

出力

各テストケースについて、答えを表す数値を1行で出力してください。絶対誤差または相対誤差が $10^{-9}$ を超えない場合に正解とみなされます。

入出力例

入力 1

0 0 0 2 4 2 4 0
0 0 0 1 2 1 2 0
2 1 4 2
1 1

出力 1

1.0000000000

入力 2

0 0 0 3 6 3 6 0
0 1 1 0 3 2 2 3
0 0 4 2
0 3

出力 2

1.2272623352