Loli được tham dự một cuộc thi Robot siêu cháy. BTC ra luật chơi như sau:

Robot được đặt ở góc trên cùng bên trái của một lưới các ô gồm ~n~ hàng và ~m~ cột. Góc trên bên trái được định nghĩa là ô ~(1,1)~.

Trong một bước, nó có thể di chuyển tới một ô liền kề với ô ~(i,j)~ hiện tại:

• ~(x,y)→(x,y+1)~;
• ~(x,y)→(x+1,y)~;
• ~(x,y)→(x,y-1)~;
• ~(x,y)→(x-1,y)~.

Robot không thể di chuyển ra ngoài lưới.

Tuy nhiên nếu chỉ có vậy thì quá dễ. BTC quyết định đặt thêm một chùm laser chết chóc. BTC đặt chùm laser đó ở ô ~(s_x,s_y)~. Nếu robot đi vào ô nào đó có khoảng cách nhỏ hơn hoặc bằng ~d~ so với chùm laser, thì robot sẽ bị pay màu.

Khoảng cách giữa hai ô ~(x_1,y_1)~ và ~(x_2,y_2)~ được định nghĩa là ~|x_1-x_2|+|y_1-y_2|~.

Loli muốn biết số bước nhỏ nhất mà robot có thể thực hiện để đi từ ô ~(1,1)~ đến ô ~(n,m)~ mà không bị pay màu hoặc di chuyển ra ngoài lưới. Nếu không thể đến ô ~(n,m)~, hãy in ~-1~.

Chùm laser không ở ô bắt đầu, cũng không ở ô kết thúc. Khoảng cách từ ô xuất phát đến chùm laser luôn lớn hơn ~d~.

Input:

Bài này có nhiều test nhỏ trong một file test, các bạn chú ý.

Lấy từ tệp DEADLASER.INP gồm:

• Dòng đầu tiên chứa một số nguyên dương ~T~ là số test nhỏ (~T\le 10~).
• Có ~T~ test nhỏ, mỗi test nhỏ có cấu trúc như sau:
  • Dòng đầu tiên chứa hai số nguyên ~n, m~ là số hàng và số cột của lưới ~(2\le n,m\le 10^9)~;
  • Dòng thứ hai chứa hai số nguyên ~s_x, s_y~ là tọa độ chùm laser (~1\le s_x \le n,\ 1\le s_y \le m~);
  • Dòng thứ ba chứa số nguyên ~d~, là bán kính hoạt động của chùm laser theo quy cách trên (~0\le d\le n+m~).

Output:

Ghi ra tệp DEADLASER.OUT gồm:

• ~T~ dòng, dòng thứ ~i~ chứa một số nguyên tương ứng với đáp án của test nhỏ thứ ~i~. Nếu không thể đến ô ~(n,m)~, hãy in ~-1~.

Sample Input 1

2
2 3 
1 3 
0
2 3 
1 3 
1

Sample Output 1

3
-1

Sample Input 2

1
5 5 
3 4 
1

Sample Output 2

8

Giải thích

Minh họa test 1.1:

Vùng màu đỏ là vùng hoạt động của chùm Laser. Để đến đích, ta cần đi vòng qua nó. Mất 3 bước để đi tới đích.

Minh họa test 1.2:

Ta không thể đi đến đích được do nó nằm trong vùng hoạt động của laser.

Minh họa test 2:

Ràng buộc

• ~1\le T\le 10~.
• Có ~20\%~ test có ~n,m\le 100~;
• Có ~20\%~ test có ~n,m\le 10^3~;
• Có ~20\%~ test có ~n,m\le 10^4~;
• Các test còn lại không có ràng buộc gì thêm.