Có một sự thật toán học nổi tiếng rằng nếu bạn đặt một tấm bản đồ của một công viên hoàn toàn bên trong công viên đó, thì sẽ tồn tại một điểm trên bản đồ trùng với điểm mà nó đại diện.

Mio rất thích sự thật này nên cô ấy đã đặt một tấm bản đồ của công viên yêu thích của mình hoàn toàn bên trong công viên đó. Công viên $P$ có thể được biểu diễn bằng một hình chữ nhật. Bản đồ của công viên chỉ đơn giản là một phiên bản nhỏ hơn (hoặc bằng) của công viên được in trên giấy. Bản đồ đồng dạng với hình chữ nhật ban đầu. Mỗi điểm trên bản đồ tương ứng với một điểm trong công viên thông qua phép biến hình đồng dạng.

Chúng ta có thể định nghĩa bản đồ một cách hình thức: Bản đồ là một hình chữ nhật $M$ (có kích thước nhỏ hơn hoặc bằng) cùng với một số thực dương $r$ và một hàm song ánh $f : M \to P$ thỏa mãn:

• Với mọi cặp điểm khác nhau $a, b \in M$, $|f(a) - f(b)|/|a - b| = r$.

$|x - y|$ biểu diễn khoảng cách Euclid giữa hai điểm $x$ và $y$.

Giống như trong nhiều trò chơi, Mio có thể dịch chuyển tức thời bằng cách sử dụng bản đồ. Cụ thể, khi Mio đang ở một điểm $x$ nào đó trên bản đồ (bao gồm cả biên), cô ấy có thể dịch chuyển đến điểm tương ứng $f(x)$ trong công viên. Cô ấy cũng có thể chọn không dịch chuyển. Điều ngược lại cũng đúng. Khi cô ấy đang ở điểm $y$ trong công viên (bao gồm cả biên), cô ấy có thể dịch chuyển đến điểm $f^{-1}(y)$ trên bản đồ đại diện cho vị trí hiện tại của cô ấy. Và cô ấy cũng có thể chọn không dịch chuyển.

Mio có thể dịch chuyển tối đa $n$ lần (và ít nhất 0 lần). Mỗi lần dịch chuyển mất $k$ giây. Mio cũng có thể đi bộ với tốc độ 1 đơn vị mỗi giây.

Cho hai điểm $s$ và $t$, hãy tìm thời gian tối thiểu Mio cần để đi từ $s$ đến $t$.

Mỗi lần dịch chuyển có thể theo bất kỳ hướng nào (từ bản đồ đến công viên, hoặc từ công viên đến bản đồ). Bản đồ có thể được đặt ngược. Vì bản đồ nằm bên trong công viên, có khả năng Mio đang ở trên bản đồ và trong công viên cùng một lúc. Trong trường hợp này, cô ấy có thể dịch chuyển theo bất kỳ hướng nào.

Ví dụ, trong hình dưới đây, công viên là $ABCD$, và bản đồ là $A'B'C'D'$. Khi Mio ở bên trong bản đồ, cô ấy đang ở trên bản đồ và trong công viên cùng một lúc. Khi cô ấy ở điểm $D'$, cô ấy có thể dịch chuyển từ bản đồ đến công viên (đến $D$), và từ công viên đến bản đồ (đến $D''$).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $T$ ($1 \le T \le 100$) biểu thị số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa 4 đỉnh của hình chữ nhật biểu diễn công viên. Các đỉnh được đưa ra theo thứ tự cùng chiều hoặc ngược chiều kim đồng hồ. Đảm bảo rằng 4 đỉnh là phân biệt.

Dòng thứ hai chứa 4 đỉnh của hình chữ nhật biểu diễn bản đồ. Đỉnh thứ $i$ của bản đồ tương ứng với đỉnh thứ $i$ của công viên với mọi $1 \le i \le 4$. Lưu ý rằng bạn có thể xác định xem bản đồ có bị đặt ngược hay không dựa trên thứ tự các đỉnh. Các đỉnh được đưa ra theo thứ tự cùng chiều hoặc ngược chiều kim đồng hồ. Đảm bảo rằng bản đồ nằm bên trong công viên. (Biên của bản đồ có thể cắt biên của công viên tại 1 hoặc nhiều điểm.) Đảm bảo rằng bản đồ là hợp lệ, nghĩa là tồn tại một số thực dương và một hàm song ánh từ bản đồ đến công viên thỏa mãn định nghĩa trên.

Dòng thứ ba chứa hai điểm $s$ và $t$. Đảm bảo rằng $s$ và $t$ nằm bên trong (hoặc trên biên của) công viên.

Dòng thứ tư chứa hai số nguyên $k, n$ ($0 \le k \le 2 \times 10^6, 0 \le n \le 100$), thời gian mỗi lần dịch chuyển cần và số lần dịch chuyển tối đa.

Mỗi điểm trong dữ liệu vào được biểu diễn bằng một cặp số nguyên có giá trị tuyệt đối không quá $2 \times 10^6$. Các số nguyên được phân tách bằng các khoảng trắng đơn.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số duy nhất biểu thị câu trả lời trên một dòng. Câu trả lời của bạn được coi là đúng nếu sai số tuyệt đối hoặc tương đối không vượt quá $10^{-9}$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

1.0000000000
1.2272623352