The robot is placed in the top left corner of a grid, consisting of $n$ rows and $m$ columns, in a cell $(1, 1)$.

In one step, it can move into a cell, adjacent by a side to the current one:

$(x, y) \rightarrow (x, y + 1)$;

$(x, y) \rightarrow (x + 1, y)$;

$(x, y) \rightarrow (x, y - 1)$;

$(x, y) \rightarrow (x - 1, y)$.

The robot can't move outside the grid.

The cell $(s_x, s_y)$ contains a deadly laser. If the robot comes into some cell that has distance less than or equal to $d$ to the laser, it gets evaporated. The distance between two cells $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.

Print the smallest number of steps that the robot can take to reach the cell $(n, m)$ without getting evaporated or moving outside the grid. If it's not possible to reach the cell $(n, m)$, print -1.

The laser is neither in the starting cell, nor in the ending cell. The starting cell always has distance greater than $d$ to the laser.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The only line of each testcase contains five integers $n, m, s_x, s_y, d$ ($2 \le n, m \le 1000$; $1 \le s_x \le n$; $1 \le s_y \le m$; $0 \le d \le n + m$) — the size of the grid, the cell that contains the laser and the evaporating distance of the laser.

The laser is neither in the starting cell, nor in the ending cell ($(s_x, s_y) \neq (1, 1)$ and $(s_x, s_y) \neq (n, m)$). The starting cell $(1, 1)$ always has distance greater than $d$ to the laser ($|s_x - 1| + |s_y - 1| > d$).


-----Output-----

For each testcase, print a single integer. If it's possible to reach the cell $(n, m)$ from $(1, 1)$ without getting evaporated or moving outside the grid, then print the smallest amount of steps it can take the robot to reach it. Otherwise, print -1.


-----Examples-----

Input
3
2 3 1 3 0
2 3 1 3 1
5 5 3 4 1
Output
3
-1
8


-----Note-----

None

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	(n, m, sx, sy, d) = map(int, inp().split())
	a = sx - 1 > d
	b = n - sx > d
	c = sy - 1 > d
	d = m - sy > d
	if a and d or (b and c):
		print(n - 1 + m - 1)
	else:
		print(-1)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


(test, count) = (int(input()), 0)
res = []
while count < test:
	(n, m, sx, sy, d) = [int(i) for i in input().split()]
	count += 1
	if 1 >= sx - d and n <= sx + d:
		res.append('-1')
		continue
	elif 1 >= sy - d and m <= sy + d:
		res.append('-1')
		continue
	elif sx + d >= n and sy + d >= m:
		res.append('-1')
		continue
	elif sx - d <= 1 and sy - d <= 1:
		res.append('-1')
		continue
	else:
		res.append(str(m + n - 2))
print('\n'.join(res))


import sys
input = sys.stdin.readline

def int_num():
	return int(input())

def int_list():
	return list(map(int, input().split()))

def str_list():
	s = input()
	return list(s[:len(s) - 1])

def instr():
	return input().strip()

def invr():
	return map(int, input().split())

def solve():
	(n, m, x, y, d) = int_list()
	a = x - d <= 1
	b = y - d <= 1
	c = x + d >= n
	d = y + d >= m
	if a and b or (c and d) or (b and d) or (a and c):
		ans = -1
	else:
		ans = n + m - 2
	print(ans)

def main():
	t = int_num()
	while t:
		solve()
		t -= 1
	return
main()


import sys
input = sys.stdin.readline
t = int(input())

def solve(n, m, sx, sy, d):
	l = sy - d <= 1
	r = sy + d >= m
	u = sx - d <= 1
	d = sx + d >= n
	if l == 0 and d == 0 or (u == 0 and r == 0):
		return n + m - 2
	else:
		return -1
for _ in range(t):
	(n, m, sx, sy, d) = [int(x) for x in input().split()]
	print(solve(n, m, sx, sy, d))


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
mod = 10 ** 9 + 7
ANS = []
input = stdin.readline

def solve():
	pass
t = int(input())
for i in range(t):
	(n, m, sx, sy, d) = map(int, input().split())
	if sx - 1 > d and m - sy > d or (sy - 1 > d and n - sx > d):
		print(n - 1 + m - 1)
	else:
		print(-1)


import sys
import math

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def test_ok(ok):
	print('YES' if ok else 'NO')

def main():
	for _ in range(int(input())):
		(n, m, sx, sy, d) = get_ints()
		if min(sx - 1, m - sy) <= d and min(n - sx, sy - 1) <= d:
			print(-1)
		else:
			print(n + m - 2)
main()


for s in [*open(0)][1:]:
	(n, m, x, y, d) = map(int, s.split())
	print((-1, n + m - 2)[max(min(x - 1, m - y), min(y - 1, n - x)) > d])


import sys
t = int(input())
while t > 0:
	(a, b, c, d, e) = map(int, sys.stdin.readline().split())
	if c - e <= 1 and d - e <= 1:
		print(-1)
	elif c + e >= a and d + e >= b:
		print(-1)
	elif c + e >= a and c - e <= 1:
		print(-1)
	elif d + e >= b and d - e <= 1:
		print(-1)
	else:
		print(a + b - 2)
	t -= 1


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	(n, m, x, y, d) = invr()
	Y = False
	X = False
	if y - d > 1 and x + d < n or (y + d < m and x - d > 1):
		print(n - 1 + (m - 1))
	else:
		print(-1)


import sys
inp = sys.stdin.readline
out = sys.stdout.write
for _ in range(int(inp())):
	(x, y, x1, y1, r) = map(int, inp().split())
	right = x - x1 > r
	top = y1 - 1 > r
	left = x1 - 1 > r
	bottom = y - y1 > r
	if right and top or (left and bottom):
		out(f'{x + y - 2}\n')
	else:
		out('-1\n')


import sys
readline = sys.stdin.readline
N = int(readline())
for _ in range(N):
	(H, W, X, Y, D) = map(int, readline().split())
	if X + D >= H and Y + D >= W:
		print(-1)
	elif X - D <= 1 and Y - D <= 1:
		print(-1)
	elif X - D <= 1 and X + D >= H:
		print(-1)
	elif Y - D <= 1 and Y + D >= W:
		print(-1)
	else:
		print(H + W - 2)


t = int(input())
g = []
for x in range(t):
	h = input()
	h = [int(a) for a in h.split()]
	n = h[0]
	m = h[1]
	sx = h[2]
	sy = h[3]
	d = h[4]
	if sx + d >= n and sx - d <= 1 or (sy + d >= m and sy - d <= 1) or (sx + d >= n and sy + d >= m) or (sx - d <= 1 and sy - d <= 1):
		g.append(-1)
	else:
		g.append(n + m - 2)
for i in g:
	print(i)


res = []
for _ in range(int(input())):
	(n, m, sx, sy, d) = map(int, input().split())
	r = n - 1 + (m - 1)
	if n - sx <= d and sx - 1 <= d:
		r = -1
	if m - sy <= d and sy - 1 <= d:
		r = -1
	if n - sx <= d and m - sy <= d:
		r = -1
	if sx - 1 <= d and sy - 1 <= d:
		r = -1
	res.append(r)
print(*res, sep='\n')


import sys
input = sys.stdin.readline
import math
import copy
import heapq
import itertools
n = int(input())
for i in range(n):
	arr = list(map(int, input().split()))
	top = True
	bottom = True
	left = True
	right = True
	if arr[2] + arr[4] >= arr[0]:
		bottom = False
	if arr[2] - arr[4] <= 1:
		top = False
	if arr[3] + arr[4] >= arr[1]:
		right = False
	if arr[3] - arr[4] <= 1:
		left = False
	if not right and (not bottom) or (not top and (not left)) or (not right and (not left)) or (not top and (not bottom)):
		print(-1)
	else:
		print(arr[0] + arr[1] - 2)


import sys
input = sys.stdin.readline

def solve():
	(n, m, sx, sy, d) = map(int, input().split())
	if sx - d > 1 and sy + d < m:
		return n - 1 + (m - 1)
	if sx + d < n and sy - d > 1:
		return n - 1 + (m - 1)
	return -1
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline
from collections import deque
t = int(input())
for i in range(t):
	(n, m, x, y, d) = map(int, input().split())
	v = 1
	if x + d >= n and x - d <= 1:
		v = 0
	if x + d >= n and y + d >= m:
		v = 0
	if y + d >= m and y - d <= 1:
		v = 0
	if x - d <= 1 and y - d <= 1:
		v = 0
	if abs(n - x) + abs(m - y) <= d:
		v = 0
	if abs(1 - x) + abs(1 - y) <= d:
		v = 0
	if v:
		print(n + m - 2)
	else:
		print(-1)


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)

def Solve():
	for t in range(int(input())):
		(n, m, x, y, d) = map(int, input().split())
		if x - d <= 1 and y - d <= 1 or (x + d >= n and y + d >= m) or (x - d <= 1 and x + d >= n) or (y - d <= 1 and y + d >= m):
			print(-1)
		else:
			print(n + m - 2)
Solve()


def fun(n, m, sx, sy, d):
	con1 = abs(sx - n) <= d
	con2 = abs(sy - m) <= d
	con3 = abs(sx - 1) <= d
	con4 = abs(sy - 1) <= d
	count = 0
	if con1:
		count += 1
	if con2:
		count += 1
	if con3:
		count += 1
	if con4:
		count += 1
	if sx == n and sy == m:
		return -1
	elif sx == 1 and sy == 1:
		return -1
	elif sx == n:
		if con3 or con2:
			return -1
	elif sy == m:
		if con1 or con4:
			return -1
	elif sx == 1:
		if con1 or con4:
			return -1
	elif sy == 1:
		if con3 or con2:
			return -1
	elif count == 2 and con3 and con2:
		return n + m - 2
	elif count == 2 and con4 and con1:
		return n + m - 2
	elif count >= 2:
		return -1
	else:
		return n + m - 2
	return n + m - 2
ans = []
t = int(input())
for i in range(t):
	l = input()
	li = l.split()
	ans.append(fun(int(li[0]), int(li[1]), int(li[2]), int(li[3]), int(li[4])))
for i in ans:
	print(i)


import sys
import queue

class Maze:

	def __init__(self, q):
		self.n = int(q[0])
		self.m = int(q[1])
		self.s_x = int(q[2])
		self.s_y = int(q[3])
		self.d = int(q[4])
		self.laser_blocks_up = False
		self.laser_blocks_down = False
		self.laser_blocks_left = False
		self.laser_blocks_right = False
		if self.s_x - self.d <= 1:
			self.laser_blocks_left = True
		if self.s_x + self.d >= self.n:
			self.laser_blocks_right = True
		if self.s_y - self.d <= 1:
			self.laser_blocks_up = True
		if self.s_y + self.d >= self.m:
			self.laser_blocks_down = True

	def x_y_to_idx(self, x, y):
		return x - 1 + (y - 1) * self.n

	def get_num_of_moves_to_exit(self):
		if self.laser_blocks_right and self.laser_blocks_left:
			return -1
		if self.laser_blocks_up and self.laser_blocks_down:
			return -1
		if self.laser_blocks_down and self.laser_blocks_right:
			return -1
		if self.laser_blocks_up and self.laser_blocks_left:
			return -1
		return self.m - 1 + (self.n - 1)
n = int(sys.stdin.readline().strip())
for i in range(n):
	q = sys.stdin.readline().strip().split()
	maze = Maze(q)
	print(maze.get_num_of_moves_to_exit())


import sys
n = int(sys.stdin.readline())
for _ in range(n):
	[n, m, sx, sy, d] = list(map(int, sys.stdin.readline().strip().split()))
	u = sx - d <= 1
	b = sx + d >= n
	l = sy - d <= 1
	r = sy + d >= m
	if (l or b) and (r or u):
		print(-1)
	else:
		print(m + n - 2)


def ans(n, m, x, y, d):
	c = min(abs(x - 1), abs(y - m))
	c2 = min(abs(y - 1), abs(x - n))
	if c <= d and c2 <= d:
		return -1
	else:
		return n + m - 2
n = int(input())
sol = []
for i in range(n):
	(n, m, x, y, d) = map(int, input().split())
	sol.append(ans(n, m, x, y, d))
for i in sol:
	print(i)


t = int(input())
final_list = []
for i in range(t):
	(n, m, sx, sy, d) = map(int, input().split())
	if sx + d < n and sy - d > 1:
		final_list += [n - 1 + (m - 1)]
	elif sx - d > 1 and sy + d < m:
		final_list += [n - 1 + (m - 1)]
	else:
		final_list += [-1]
for i in final_list:
	print(i)


p = int(input())
a = [0] * p
for i in range(p):
	(n, m, sx, sy, d) = map(int, input().split())
	r = -1
	if sy + d < m and sx - d > 1 or (sx + d < n and sy - d > 1):
		r = m + n - 2
	if abs(sx - n) + abs(sy - m) <= d:
		r = -1
	a[i] = r
for i in range(p):
	print(a[i])


a = int(input())
list_of_outputs = []
for i in range(a):
	steps = -1
	arr = [int(x) for x in input().split()]
	n = arr[0]
	m = arr[1]
	sr = arr[2]
	sc = arr[3]
	d = arr[4]
	if sr - d > 1 and sc + d < m or (sc - d > 1 and sr + d < n):
		steps = n + m - 2
	list_of_outputs.append(steps)
for otveti in list_of_outputs:
	print(otveti)


nums = int(input())
results = []

def calc(n, m, s_x, s_y, d):
	left = s_x - d > 1
	top = s_y + d < m
	right = s_x + d < n
	bottom = s_y - d > 1
	if left and top or (right and bottom):
		return n + m - 2
	return -1
for row in range(nums):
	[n, m, s_x, s_y, d] = [int(n) for n in input().split()]
	result = calc(n, m, s_x, s_y, d)
	results.append(result)
for result in results:
	print(result)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	a = list(map(int, input().split()))
	(n, m) = (a[0], a[1])
	(x, y) = (a[2], a[3])
	d = a[4]
	count = []
	if d + x >= n:
		count.append('d')
	if d + y >= m:
		count.append('r')
	if x - d <= 1:
		count.append('u')
	if y - d <= 1:
		count.append('l')
	check = False
	if len(count) == 2:
		check = True
		if 'r' in count and 'u' in count:
			check = False
		elif 'd' in count and 'l' in count:
			check = False
	if abs(n - x) + abs(m - y) <= d or abs(1 - x) + abs(1 - y) <= d or len(count) > 2 or check:
		print('-1')
		continue
	else:
		print(abs(n - 1) + abs(m - 1))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	(n, m, x, y, d) = inlt()
	min_x = max(1, x - d)
	max_x = min(n, x + d)
	min_y = max(1, y - d)
	max_y = min(m, y + d)
	if min_x == 1 and max_x == n:
		return -1
	if min_y == 1 and max_y == m:
		return -1
	if min_x == 1 and min_y == 1:
		return -1
	if max_x == n and max_y == m:
		return -1
	return m + n - 2
for _ in range(inp()):
	print(solve())


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
testCasesNum = inp()
for _ in range(testCasesNum):
	arr = list(map(int, input().split()))
	(m, n) = (arr[0], arr[1])
	(a, b) = (arr[2] - 1, arr[3] - 1)
	l = m + n - 2
	x = [a, m - 1]
	y = [0, b]
	flag = 1
	for (i, j) in zip(x, y):
		if abs(i - arr[2] + 1) + abs(j - arr[3] + 1) <= arr[4]:
			flag = 0
	if flag:
		print(l)
		continue
	else:
		flag = 1
	x = [0, a]
	y = [b, n - 1]
	for (i, j) in zip(x, y):
		if abs(i - arr[2] + 1) + abs(j - arr[3] + 1) <= arr[4]:
			flag = 0
	if flag:
		print(l)
	else:
		print(-1)


from tabnanny import check
t = int(input())
result = []

def dist(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])
for i in range(t):
	(n, m, x, y, d) = list(map(int, input().split()))
	if (dist((x, 1), (x, y)) <= d or dist((n, y), (x, y)) <= d) and (dist((x, m), (x, y)) <= d or dist((1, y), (x, y)) <= d):
		result.append(-1)
		continue
	result.append(m - 1 + n - 1)
list(map(print, result))


import sys
from collections import *
import bisect
import math
from functools import lru_cache
for _ in range(int(input())):
	(n, m, x, y, d) = map(int, sys.stdin.readline().split())
	if (x, y) == (1, 1) or (x, y) == (n, m):
		print(-1)
	else:
		flag1 = True
		x1 = 1
		y1 = y
		x2 = x
		y2 = m
		if abs(x - x1) + abs(y - y1) <= d or abs(x - x2) + abs(y - y2) <= d:
			flag1 = False
		flag2 = True
		x1 = x
		y1 = 1
		x2 = n
		y2 = y
		if abs(x - x1) + abs(y - y1) <= d or abs(x - x2) + abs(y - y2) <= d:
			flag2 = False
		if flag1 or flag2:
			print(n + m - 2)
		else:
			print(-1)


t = int(input())
l = []
for i in range(0, t):
	p = [int(x) for x in input().split()]
	l.append(p)
for j in range(0, t):
	n = l[j][0]
	m = l[j][1]
	sx = l[j][2]
	sy = l[j][3]
	d = l[j][4]
	if n - sy + (m - sx) <= d:
		print(-1)
	elif sy - 1 <= d and m - sy <= d:
		print(-1)
	elif sx - 1 <= d and n - sx <= d:
		print(-1)
	elif sy - 1 <= d and sx - 1 <= d:
		print(-1)
	elif m - sy <= d and n - sx <= d:
		print(-1)
	else:
		print(n - 1 + (m - 1))


n1 = int(input())
l = []
for i in range(0, n1):
	s = [int(x) for x in input().split()]
	l.append(s)
for j in range(0, n1):
	n = l[j][0]
	m = l[j][1]
	sx = l[j][2]
	sy = l[j][3]
	d = l[j][4]
	if abs(sx - n) + abs(sy - m) <= d:
		print(-1)
	elif abs(sy - m) <= d and abs(sy - 1) <= d:
		print(-1)
	elif abs(sx - 1) <= d and abs(sx - n) <= d:
		print(-1)
	elif abs(sy - 1) <= d and abs(sx - 1) <= d:
		print(-1)
	elif abs(sy - m) <= d and abs(sx - n) <= d:
		print(-1)
	else:
		print(abs(n - 1) + abs(m - 1))


import sys
ls = []
for l in sys.stdin:
	lst = l.rstrip('\n')
	if len(lst) > 0:
		ls.append(lst)
for l in ls:
	sys.stderr.write(l + '\n')
sys.stderr.write('-- output --\n')

def ins(u, mn, mx):
	return u[0] >= mn[0] and u[1] >= mn[1] and (u[0] <= mx[0]) and (u[1] <= mx[1])

def clmp(x, n):
	if x < 0:
		return 0
	if x >= n:
		return n - 1
	return x

def clp(u, n, m):
	return (clmp(u[0], n), clmp(u[1], m))

def d(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])

def solve(n, m, sx, sy, d):
	if d == 0:
		return n + m - 2
	smin = clp((sx - d, sy - d), n, m)
	smax = clp((sx + d, sy + d), n, m)
	if abs(smax[0] - smin[0]) >= n - 1 or abs(smax[1] - smin[1]) >= m - 1:
		return -1
	if ins((0, 0), smin, smax) or ins((n - 1, m - 1), smin, smax):
		return -1
	return n + m - 2
for l in ls[1:]:
	(n, m, sx, sy, d) = [int(x) for x in l.split(' ')]
	print(solve(n, m, sx - 1, sy - 1, d))


for _ in range(int(input())):
	(n, m, x, y, d) = map(int, input().split())
	ans = n + m - 2
	if x + d >= n and x - d <= 1 or (y + d >= m and y - d <= 1) or (x + d >= n and y + d >= m) or (x - d <= 1 and y - d <= 1):
		print(-1)
	else:
		print(ans)


for i in range(int(input())):
	(n, m, sx, sy, d) = map(int, input().split())
	if abs(sx - 1) > d and abs(sy - m) > d or (abs(sy - 1) > d and abs(sx - n) > d):
		print(abs(n - 1) + abs(m - 1))
	else:
		print(-1)


def solution(n, m, x, y, d):
	v1 = x + d >= n or y - d <= 1
	v2 = x - d <= 1 or y + d >= m
	if v1 and v2:
		return -1
	else:
		return m + n - 2
t = int(input())
for i in range(t):
	[n, m, x, y, d] = [int(x) for x in input().split()]
	print(solution(n, m, x, y, d))


def check1(n, m, sx, sy, d):
	if sx - d <= 1:
		return True
	if sy + d >= m:
		return True

def check2(n, m, sx, sy, d):
	if sx + d >= n:
		return True
	if sy - d <= 1:
		return True

def work():
	(n, m, sx, sy, d) = [int(i) for i in input().split()]
	if check1(n, m, sx, sy, d) and check2(n, m, sx, sy, d):
		print(-1)
	else:
		print(n + m - 2)
TC = int(input())
for i in range(TC):
	work()


standard_input = '3\n2 3 1 3 0\n2 3 1 3 1\n5 5 3 4 1\n'

def solve(r, c, sx, sy, d):
	poss = False
	if r - sy > d and sx - 1 > d:
		poss = True
	if c - sx > d and sy - 1 > d:
		poss = True
	return r + c - 2 if poss else -1
for _ in range(int(input())):
	(r, c, sx, sy, d) = map(int, input().split())
	print(solve(c, r, sx, sy, d))


def too_wide(n, m, sx, sy, d):
	return sy - d <= 1 and sy + d >= m

def too_height(n, m, sx, sy, d):
	return sx - d <= 1 and sx + d >= n

def left_corner(n, m, sx, sy, d):
	return sx - d <= 1 and sy - d <= 1

def right_corner(n, m, sx, sy, d):
	return sx + d >= n and sy + d >= m

def solve():
	(n, m, sx, sy, d) = map(int, input().split(' '))
	possible = not too_wide(n, m, sx, sy, d) and (not too_height(n, m, sx, sy, d)) and (not left_corner(n, m, sx, sy, d)) and (not right_corner(n, m, sx, sy, d))
	return n - 1 + (m - 1) if possible else -1

def main():
	t = int(input())
	for i in range(t):
		res = solve()
		print(res)
main()


for _ in range(int(input())):
	(n, m, lx, ly, d) = map(int, input().split())
	if ly - d > 1 and lx + d < n or (lx - d > 1 and ly + d < m):
		print(n + m - 2)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, m, x, y, d) = map(int, input().split())
	if x - d <= 1 and y - d <= 1:
		print(-1)
		continue
	if x + d >= n and y + d >= m:
		print(-1)
		continue
	if x - d <= 1 and x + d >= n:
		print(-1)
		continue
	if y - d <= 1 and y + d >= m:
		print(-1)
		continue
	print(n + m - 2)


t = int(input())
for i in range(t):
	(n, m, x, y, d) = map(int, input().split())
	if (x - d <= 1 or y + d >= m) and (y - d <= 1 or x + d >= n):
		print(-1)
	else:
		print(n - 1 + m - 1)


t = int(input())
for _ in range(t):
	(n, m, sx, sy, d) = map(int, input().split())
	if not (sy - d <= 1 or sx + d >= n) or not (sy + d >= m or sx - d <= 1):
		print(n + m - 2)
	else:
		print(-1)


t = eval(input())
for k in range(t):
	(n, m, sx, sy, d) = list(map(int, input().split()))
	if sx - 1 > d and m - sy > d or (sy - 1 > d and n - sx > d):
		print(n + m - 2)
	else:
		print(-1)


def fun():
	(n, m, a, b, d) = map(int, input().split())
	a = a - 1
	b = b - 1
	x1 = n - a - 1
	y1 = m - b - 1
	if a <= d and x1 <= d:
		print(-1)
		return
	if b <= d and y1 <= d:
		print(-1)
		return
	if a <= d and b <= d:
		print(-1)
		return
	if x1 <= d and y1 <= d:
		print(-1)
		return
	print(n + m - 2)
t = int(input())
while t:
	fun()
	t -= 1


from calendar import month_name

def distance(x1: int, y1: int, x2: int, y2: int) -> int:
	return abs(x1 - x2) + abs(y1 - y2)

def solve(m: int, n: int, s1: int, s2: int, d: int) -> int:
	if (s1 - d > 1 and s2 + d < n or (s1 + d < m and s2 - d > 1)) and distance(m, n, s1, s2) > d:
		return m + n - 2
	else:
		return -1
t = int(input())
ans = []
for _ in range(t):
	(m, n, s1, s2, d) = [int(x) for x in input().split()]
	ans.append(solve(m, n, s1, s2, d))
for a in ans:
	print(a)


def fun(n, m, sx, sy, d):
	if m - sy > d and sx - 1 > d or (n - sx > d and sy - 1 > d):
		print(n + m - 2)
	else:
		print(-1)

def main():
	t = int(input())
	for _ in range(t):
		(n, m, sx, sy, d) = map(int, input().split())
		fun(n, m, sx, sy, d)
main()


testCases = int(input())
for i in range(testCases):
	line = input()
	(n, m, sx, sy, d) = map(int, line.split(' '))
	if (sx - d <= 1 or sy + d >= m) and (sx + d >= n or sy - d <= 1):
		print(-1)
		continue
	print(n + m - 2)


t = int(input())
for i in range(0, t):
	(n, m, sx, sy, d) = map(int, input().split())
	if (sx - 1 <= d or sy + d >= m) and (sy - 1 <= d or sx + d >= n):
		print(-1)
	else:
		print(n + m - 2)


t = int(input())
for i in range(t):
	lis = input().split()
	(n, m, sx, sy, d) = (int(lis[0]), int(lis[1]), int(lis[2]), int(lis[3]), int(lis[4]))
	if sx + d >= n and sx - d <= 1:
		res = -1
	elif sy + d >= m and sy - d <= 1:
		res = -1
	elif sx + d >= n and sy + d >= m:
		res = -1
	elif sx - d <= 1 and sy - d <= 1:
		res = -1
	else:
		res = m + n - 2
	print(res)


for _ in range(int(input())):
	(n, m, sx, sy, d) = map(int, input().split())
	if sx + d < n and sy - d > 1:
		print(n + m - 2)
	elif sx - d > 1 and sy + d < m:
		print(n + m - 2)
	else:
		print(-1)


for i in range(int(input())):
	(n, m, sx, sy, d) = map(int, input().split())
	if d == m - 1 or d == n - 1:
		print(-1)
	elif n - sx <= d and sx - 1 <= d:
		print(-1)
	elif m - sy <= d and n - sx <= d:
		print(-1)
	elif sy - 1 <= d and sx - 1 <= d:
		print(-1)
	elif sy - 1 <= d and m - sy <= d:
		print(-1)
	elif sx == n and m - sy <= d:
		print(-1)
	elif sy == m and n - sx <= d:
		print(-1)
	else:
		print(n + m - 2)
		continue


t = int(input())
for _ in range(t):
	(row, col, sx, sy, d) = map(int, input().split())
	res = -1
	if (sx - 1 <= d or col - sy <= d) and (row - sx <= d or sy - 1 <= d):
		pass
	else:
		res = row + col - 2
	print(res)


for pythonic__Python in range(int(input())):
	(n, m, s1, s2, d) = map(int, input().split())
	if s1 + d >= n and s2 + d >= m or (s1 - d <= 1 and s2 - d <= 1) or (s1 + d >= n and s1 - d <= 1) or (s2 + d >= m and s2 - d <= 1):
		print(-1)
	else:
		print(n + m - 2)


for _ in range(int(input())):
	(m, n, a, b, d) = map(int, input().split())
	if d < b - 1 and d < m - a or (d < a - 1 and d < n - b):
		print(m + n - 2)
	else:
		print(-1)


for _ in range(int(input())):
	(n, m, s, e, d) = map(int, input().split())
	if s - d > 1 and e + d < m or (e - d > 1 and s + d < n):
		print(n + m - 2)
	else:
		print(-1)


def solve():
	(n, m, s, t, d) = map(int, input().split())
	ans = -1
	if min(s - 1, m - t) <= d and min(n - s, t - 1) <= d:
		ans = -1
	else:
		ans = m + n - 2
	print(ans)
multi = True
tt = 1
if multi:
	tt = int(input())
for i in range(tt):
	solve()


t = int(input())
while t:
	(n, m, sx, sy, d) = map(int, input().split())
	ans = -1
	if sx + d < n and sy - d > 1 or (sx - d > 1 and sy + d < m):
		ans = n + m - 2
	print(ans)
	t -= 1


n = int(input())
inputData = []
for i in range(n):
	(Nx, Ny, Sx, Sy, Dd) = map(int, input().split())
	if Sy + Dd >= Ny and Sx + Dd >= Nx or (Sy - Dd <= 1 and Sx - Dd <= 1) or (Sy + Dd >= Ny and Sy - Dd <= 1) or (Sx + Dd >= Nx and Sx - Dd <= 1):
		print('-1')
	else:
		print(abs(1 - Nx) + abs(1 - Ny))


for _ in range(int(input())):
	(n, m, si, sj, d) = map(int, input().split())
	met_walls = 0
	if si - d <= 1 or sj + d >= m:
		met_walls += 1
	if si + d >= n or sj - d <= 1:
		met_walls += 1
	if met_walls < 2:
		print(m + n - 2)
	else:
		print(-1)


test = int(input())
for t in range(test):
	variables = list(map(int, input().split()))
	length = variables[0]
	width = variables[1]
	lasor_X = variables[2]
	lasor_Y = variables[3]
	distance = variables[4]
	if lasor_X + distance < length and lasor_Y - distance > 1 or (lasor_X - distance > 1 and lasor_Y + distance < width):
		print(length + width - 2)
	else:
		print(-1)


testCase = int(input())
for index in range(testCase):
	(n, m, s_x, s_y, d) = map(int, input().split())
	if (min(s_y - 1, n - s_x) <= d) & (min(m - s_y, s_x - 1) <= d):
		print(int(-1))
	else:
		print(n + m - 2)


sets = int(input())
for i in range(sets):
	a = list(map(int, input().split()))
	(n, m, sx, sy, d) = (a[0], a[1], a[2], a[3], a[4])
	if sx - d > 1 and sy + d < m or (sy - d > 1 and sx + d < n):
		print(n + m - 2)
	else:
		print(-1)


def solve(n, m, x, y, d):
	touch_right_border = x + d >= n
	touch_bottom_border = y + d >= m
	touch_left_border = x - d <= 1
	touch_top_border = y - d <= 1
	if touch_right_border and touch_bottom_border or (touch_right_border and touch_left_border) or (touch_top_border and touch_bottom_border) or (touch_top_border and touch_left_border):
		return -1
	return n + m - 2
t = int(input())
for _ in range(t):
	(n, m, x, y, d) = [int(e) for e in input().split()]
	print(solve(n, m, x, y, d))


t = int(input())
for i in range(t):
	(n, m, Sx, Sy, d) = map(int, input().split())
	if Sx - d <= 1 and Sx + d >= n or (Sy - d <= 1 and Sy + d >= m) or (Sx - d <= 1 and Sy - d <= 1) or (Sx + d >= n and Sy + d >= m):
		print('-1')
	else:
		k = n + m - 2
		print(k)