Một robot lau dọn được đặt trên sàn của một căn phòng hình chữ nhật, xung quanh được bao bởi các bức tường. Sàn gồm ~n~ hàng và ~m~ cột. Các hàng của sàn được đánh số từ ~1~ đến ~n~ theo thứ tự từ trên xuống dưới, và các cột của sàn được đánh số từ ~1~ đến ~m~ theo thứ tự từ trái sang phải. Ô tại giao điểm của hàng thứ ~r~ và cột thứ ~c~ được ký hiệu là ~(r,c)~. Vị trí ban đầu của robot là ~(r_b, c_b)~.

Trong một giây, robot di chuyển ~dr~ hàng và ~dc~ cột; tức là sau một giây, robot đi từ ô ~(r, c)~ đến ô ~(r + dr, c + dc)~. Ban đầu, ~dr = 1~, ~dc = 1~. Nếu có một bức tường dọc (tường bên trái hoặc bên phải) theo hướng di chuyển, thì ~dc~ sẽ bị phản xạ trước khi di chuyển, nên giá trị mới của ~dc~ là ~-dc~. Tương tự, nếu có một bức tường ngang (tường phía trên hoặc phía dưới) theo hướng di chuyển, thì ~dr~ sẽ bị phản xạ trước khi di chuyển, nên giá trị mới của ~dr~ là ~-dr~.

Mỗi giây (bao gồm cả thời điểm trước khi robot bắt đầu di chuyển), các ô nằm trên cùng hàng hoặc cùng cột với vị trí hiện tại của robot sẽ được con robot lau sạch một lần. Ô vị trí hiện tại của con robot cũng chỉ được lau sạch một lần.

Tại thời điểm ~t~, định nghĩa:

• độ sạch của một ô trên sàn là số lần mà ô đó được lau sạch,

• độ sạch của sàn nhà là độ sạch nhỏ nhất trong số các ô trên mặt sàn.

Cho kích thước sàn ~n~ và ~m~, số nguyên ~k~, cùng vị trí ban đầu của robot ~(r_b, c_b)~. Hãy tìm thời điểm ~t~ nhỏ nhất sao cho khi robot lau sàn đến thời điểm ~t~, sàn nhà có độ sạch là ~k~.

Input

Mỗi bộ dữ liệu gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 1000~). Phần mô tả các test case như sau.

Mỗi test case chỉ gồm một dòng, chứa năm số nguyên ~n~, ~m~, ~k~, ~r_b~, ~c_b~ (~2 \le n, m \le 20\,000~, ~1 \le k \le 10^9~, ~1 \le r_b \le n~, ~1 \le c_b \le m~) — kích thước của sàn nhà, độ sạch của sàn nhà cần đạt được, và vị trí ban đầu của robot.

Đảm bảo rằng:

• tổng ~n~ qua các test case không quá ~20\,000~,

• tổng ~m~ qua các test case không quá ~20\,000~.

Output

Với mỗi test case, in ra một số nguyên — thời gian tối thiểu để sàn nhà đạt được độ sạch ~k~.

Scoring

Sample Input 1

4
3 4 2 2 1
9 8 1 5 6
3 3 2 1 2
2 2 10 1 1

Sample Output 1

7
9
3
19

Notes

Hình trong đề bài là minh họa cho ví dụ đầu tiên.

Trong ví dụ thứ hai, sàn có kích thước ~9\times 8~, mỗi ô cần được lau sạch ít nhất ~k=1~ lần. Robot xuất phát tại ô ~(5, 6)~.

Trong ví dụ thứ ba, sàn có kích thước ~3\times 3~, mỗi ô cần được lau sạch ít nhất ~k=2~ lần. Robot xuất phát tại ô ~(1, 2)~.

Trong ví dụ thứ tư, sàn có kích thước ~2\times 2~, mỗi ô cần được lau sạch ít nhất ~k=10~ lần. Robot xuất phát tại ô ~(1, 1)~. Sau mỗi giây, hai ô ~(1, 2)~ và ~(2, 1)~ đều được lau. Còn ô ~(1, 1)~ và ô ~(2, 2)~ chỉ được lau 1 lần sau 2 giây. Ô ~(1, 1)~ sẽ được lau ~10~ lần sau ~18~ giây, còn ô ~(2, 2)~ sẽ được lau ~10~ lần sau ~19~ giây. Do đó, đáp án là ~19~.