You are given four different integer points $p_1$, $p_2$, $p_3$ and $p_4$ on $\mathit{XY}$ grid.

In one step you can choose one of the points $p_i$ and move it in one of four directions by one. In other words, if you have chosen point $p_i = (x, y)$ you can move it to $(x, y + 1)$, $(x, y - 1)$, $(x + 1, y)$ or $(x - 1, y)$.

Your goal to move points in such a way that they will form a square with sides parallel to $\mathit{OX}$ and $\mathit{OY}$ axes (a square with side $0$ is allowed).

What is the minimum number of steps you need to make such a square?


-----Input-----

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

Each test case consists of four lines. Each line contains two integers $x$ and $y$ ($0 \le x, y \le 10^9$) — coordinates of one of the points $p_i = (x, y)$.

All points are different in one test case.


-----Output-----

For each test case, print the single integer — the minimum number of steps to make a square.


-----Examples-----

Input
3
0 2
4 2
2 0
2 4
1 0
2 0
4 0
6 0
1 6
2 2
2 5
4 1
Output
8
7
5


-----Note-----

In the first test case, one of the optimal solutions is shown below:

Each point was moved two times, so the answer $2 + 2 + 2 + 2 = 8$.

In the second test case, one of the optimal solutions is shown below:

The answer is $3 + 1 + 0 + 3 = 7$.

In the third test case, one of the optimal solutions is shown below:

The answer is $1 + 1 + 2 + 1 = 5$.

Source: codeforces | Difficulty: VERY_HARD
Tags: Constructive algorithms

Geometry

Sorting

Implementation

Complete search

Greedy algorithms

Mathematics

Flows and cuts


Solutions:
t = int(input())

def solvePerm(points):
	x1 = [points[0][0], points[1][0]]
	segX1 = (min(*x1), max(*x1))
	x2 = [points[2][0], points[3][0]]
	segX2 = (min(*x2), max(*x2))
	xRange = (max(0, min(*segX2) - max(*segX1)), max(*segX2) - min(*segX1))
	if xRange[1] < xRange[0]:
		return 10 ** 20
	y1 = [points[1][1], points[2][1]]
	segY1 = (min(*y1), max(*y1))
	y2 = [points[3][1], points[0][1]]
	segY2 = (min(*y2), max(*y2))
	yRange = (max(0, min(*segY2) - max(*segY1)), max(*segY2) - min(*segY1))
	if yRange[1] < yRange[0]:
		return 10 ** 20
	s = segX1[1] - segX1[0] + (segX2[1] - segX2[0])
	s += segY1[1] - segY1[0] + (segY2[1] - segY2[0])
	if yRange[0] <= xRange[1] and xRange[0] <= yRange[1]:
		pass
	else:
		d = max(yRange[0] - xRange[1], xRange[0] - yRange[1])
		s += 2 * d
	return s
from itertools import permutations
for _ in range(t):
	points = [tuple(map(int, input().split())) for _ in range(4)]
	mi = 10 ** 20
	for p in permutations(points):
		mi = min(mi, solvePerm(p))
	print(mi)


import sys
from itertools import permutations
rl = []

def gen_sort(n, x):
	if n == 4:
		rl.append(x[:])
	for i in range(n, 4):
		(x[i], x[n]) = (x[n], x[i])
		gen_sort(n + 1, x)
		(x[i], x[n]) = (x[n], x[i])
	return
gen_sort(0, [0, 1, 2, 3])
max = lambda x, y: x if x > y else y
min = lambda x, y: x if x < y else y
abs = lambda x: x if x > 0 else -x
xlr = [0, 0]
xrr = [0, 0]
dxr = [0, 0]
y_up_r = [0, 0]
y_down_r = [0, 0]
dyr = [0, 0]
T = int(sys.stdin.readline().strip())
while T > 0:
	T -= 1
	point = []
	for i in range(4):
		(a, b) = sys.stdin.readline().strip().split(' ')
		point.append([int(a), int(b)])
	res = 4000000000
	for now in rl:
		p = []
		for i in range(4):
			p.append(point[now[i]])
		xlr[0] = min(p[0][0], p[2][0])
		xlr[1] = max(p[0][0], p[2][0])
		xrr[0] = min(p[1][0], p[3][0])
		xrr[1] = max(p[1][0], p[3][0])
		dxr[0] = abs(xrr[0] - xlr[1])
		dxr[1] = abs(xrr[1] - xlr[0])
		if dxr[0] > dxr[1]:
			(dxr[0], dxr[1]) = (dxr[1], dxr[0])
		y_up_r = [min(p[0][1], p[1][1]), max(p[0][1], p[0][1])]
		y_down_r = [min(p[2][1], p[3][1]), max(p[2][1], p[3][1])]
		y_up_r[0] = min(p[0][1], p[1][1])
		y_up_r[1] = max(p[0][1], p[0][1])
		y_down_r[0] = min(p[2][1], p[3][1])
		y_down_r[1] = max(p[2][1], p[3][1])
		dyr[0] = abs(y_down_r[0] - y_up_r[1])
		dyr[1] = abs(y_down_r[1] - y_up_r[0])
		if dyr[0] > dyr[1]:
			(dyr[1], dyr[0]) = (dyr[0], dyr[1])
		ans = abs(p[2][0] - p[0][0]) + abs(p[1][0] - p[3][0]) + abs(p[1][1] - p[0][1]) + abs(p[2][1] - p[3][1])
		if dxr[1] < dyr[0]:
			ans += (dyr[0] - dxr[1]) * 2
		elif dyr[1] < dxr[0]:
			ans += (dxr[0] - dyr[1]) * 2
		res = min(res, ans)
	print(res)


from sys import stdin, stdout

def calculate(a, b, c, d, l):
	if b + l <= c:
		return d - a + c - l - b - l
	elif a + l >= d:
		return b + l - c + a + l - d
	else:
		return b - a + d - c

def calculate2(a, b, c, d, l):
	if a + l <= d:
		return c - a + (d - b)
	else:
		return c + l - d + (a + l) - b
t = int(stdin.readline())
for _ in range(t):
	points = []
	x = []
	y = []
	for foo in range(4):
		(x0, y0) = [int(x) for x in stdin.readline().split()]
		points.append((x0, y0))
		x.append(x0)
		y.append(y0)
	points.sort()
	x.sort()
	y.sort()
	answer = 9999999999999
	if points[0][1] < points[2][1] and points[0][1] < points[3][1] and (points[1][1] < points[2][1]) and (points[1][1] < points[3][1]) or (points[0][1] > points[2][1] and points[0][1] > points[3][1] and (points[1][1] > points[2][1]) and (points[1][1] > points[3][1])):
		for l in set((x[1] - x[0], x[2] - x[0], x[3] - x[0], x[2] - x[1], x[3] - x[1], x[3] - x[2], y[1] - y[0], y[2] - y[0], y[3] - y[0], y[2] - y[1], y[3] - y[1], y[3] - x[2])):
			candidatex = calculate(x[0], x[1], x[2], x[3], l) + calculate2(y[0], y[1], y[2], y[3], l)
			candidatey = calculate(y[0], y[1], y[2], y[3], l) + calculate2(x[0], x[1], x[2], x[3], l)
			answer = min(candidatex, candidatey, answer)
	else:
		for l in set((x[1] - x[0], x[2] - x[0], x[3] - x[0], x[2] - x[1], x[3] - x[1], x[3] - x[2], y[1] - y[0], y[2] - y[0], y[3] - y[0], y[2] - y[1], y[3] - y[1], y[3] - x[2])):
			candidate = calculate(x[0], x[1], x[2], x[3], l) + calculate(y[0], y[1], y[2], y[3], l)
			answer = min(candidate, answer)
	stdout.write(str(answer) + '\n')


def move(ps):
	for i in range(3):
		for j in range(i + 1, 4):
			if ps[j] < ps[i]:
				x = ps[i]
				ps[i] = ps[j]
				ps[j] = x
	ps1 = ps[:]
	if ps[0][1] > ps[1][1]:
		x = ps[0]
		ps[0] = ps[1]
		ps[1] = x
	if ps[2][1] > ps[3][1]:
		x = ps[2]
		ps[2] = ps[3]
		ps[3] = x
	dx1 = abs(ps[1][0] - ps[0][0])
	dx2 = abs(ps[3][0] - ps[2][0])
	dx_max = max(ps[3][0], ps[2][0]) - min(ps[0][0], ps[1][0])
	dx_min = max(0, min(ps[3][0], ps[2][0]) - max(ps[0][0], ps[1][0]))
	dy1 = abs(ps[3][1] - ps[1][1])
	dy2 = abs(ps[2][1] - ps[0][1])
	dy_max = max(ps[3][1], ps[1][1]) - min(ps[2][1], ps[0][1])
	dy_min = max(0, min(ps[3][1], ps[1][1]) - max(ps[2][1], ps[0][1]))
	move1 = dx1 + dx2 + dy1 + dy2 + 2 * max(0, max(dy_min, dx_min) - min(dx_max, dy_max))
	ps = ps1
	x = ps[1]
	ps[1] = ps[2]
	ps[2] = x
	if ps[0][1] > ps[1][1]:
		x = ps[0]
		ps[0] = ps[1]
		ps[1] = x
	if ps[2][1] > ps[3][1]:
		x = ps[2]
		ps[2] = ps[3]
		ps[3] = x
	dx1 = abs(ps[1][0] - ps[0][0])
	dx2 = abs(ps[3][0] - ps[2][0])
	dx_max = max(ps[3][0], ps[2][0]) - min(ps[0][0], ps[1][0])
	dx_min = max(0, min(ps[3][0], ps[2][0]) - max(ps[0][0], ps[1][0]))
	dy1 = abs(ps[3][1] - ps[1][1])
	dy2 = abs(ps[2][1] - ps[0][1])
	dy_max = max(ps[3][1], ps[1][1]) - min(ps[2][1], ps[0][1])
	dy_min = max(0, min(ps[3][1], ps[1][1]) - max(ps[2][1], ps[0][1]))
	move2 = dx1 + dx2 + dy1 + dy2 + 2 * max(0, max(dy_min, dx_min) - min(dx_max, dy_max))
	return min(move1, move2)
for i in range(int(input())):
	ps = []
	for j in range(4):
		(x, y) = map(int, input().split())
		ps.append([x, y])
	steps = str(int(move(ps)))
	print(steps)


T = int(input())
ans = [0] * T
for t in range(T):
	(X, Y) = ([0] * 4, [0] * 4)
	A = [0] * 4
	for i in range(4):
		(X[i], Y[i]) = map(int, input().split())
		A[i] = [X[i], Y[i]]
	X.sort()
	Y.sort()
	A.sort()
	cnt = 0
	for i in range(2):
		rank = 1
		for j in range(4):
			if A[i][1] < A[j][1]:
				rank += 1
		if rank <= 2:
			cnt += 1
	if cnt != 1:
		ans[t] += min(Y[2] - Y[1], X[2] - X[1]) * 2
	x_min = X[2] - X[1]
	x_max = X[3] - X[0]
	y_min = Y[2] - Y[1]
	y_max = Y[3] - Y[0]
	if x_max < y_min:
		ans[t] += X[3] - X[2] + (X[1] - X[0])
		ans[t] += Y[3] - Y[2] + (Y[1] - Y[0]) + 2 * (y_min - x_max)
	elif y_max < x_min:
		ans[t] += X[3] - X[2] + (X[1] - X[0]) + 2 * (x_min - y_max)
		ans[t] += Y[3] - Y[2] + (Y[1] - Y[0])
	else:
		ans[t] += X[3] - X[2] + (X[1] - X[0])
		ans[t] += Y[3] - Y[2] + (Y[1] - Y[0])
print(*ans, sep='\n')


from itertools import permutations, combinations
from sys import stdin, gettrace
INF = int(10000000000.0)
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def solve():
	xy = []
	for _ in range(4):
		(x, y) = map(int, inputi().split())
		xy.append((x, y))
	res = INF
	for p in combinations(range(4), 2):
		mxx1 = 0
		mnx1 = INF
		mxx2 = 0
		mnx2 = INF
		q = [i for i in range(4) if i not in p]
		mnx1 = min((xy[i][0] for i in p))
		mxx1 = max((xy[i][0] for i in p))
		mnx2 = min((xy[i][0] for i in q))
		mxx2 = max((xy[i][0] for i in q))
		mnxl = mnx2 - mxx1 if mxx1 < mnx2 else mnx1 - mxx2 if mnx1 > mxx2 else 0
		mxxl = max(mxx2 - mnx1, mxx1 - mnx2)
		xc = mxx1 - mnx1 + mxx2 - mnx2
		mny1 = min(xy[p[0]][1], xy[q[0]][1])
		mxy1 = max(xy[p[0]][1], xy[q[0]][1])
		mny2 = min(xy[p[1]][1], xy[q[1]][1])
		mxy2 = max(xy[p[1]][1], xy[q[1]][1])
		mnyl = mny2 - mxy1 if mxy1 < mny2 else mny1 - mxy2 if mny1 > mxy2 else 0
		mxyl = max(mxy2 - mny1, mxy1 - mny2)
		yc = mxy1 - mny1 + mxy2 - mny2
		c = xc + yc + 2 * max(0, max(mnxl, mnyl) - min(mxxl, mxyl))
		res = min(c, res)
		mny1 = min(xy[p[0]][1], xy[q[1]][1])
		mxy1 = max(xy[p[0]][1], xy[q[1]][1])
		mny2 = min(xy[p[1]][1], xy[q[0]][1])
		mxy2 = max(xy[p[1]][1], xy[q[0]][1])
		mnyl = mny2 - mxy1 if mxy1 < mny2 else mny1 - mxy2 if mny1 > mxy2 else 0
		mxyl = max(mxy2 - mny1, mxy1 - mny2)
		yc = mxy1 - mny1 + mxy2 - mny2
		c = xc + yc + 2 * max(0, max(mnxl, mnyl) - min(mxxl, mxyl))
		res = min(c, res)
	print(res)

def main():
	t = int(inputi())
	for _ in range(t):
		solve()
main()


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]
MOD = 998244353

def solve():
	(X, Y) = ([], [])
	for i in range(4):
		(x, y) = getInts()
		X.append(x)
		Y.append(y)
	X1 = X[:]
	Y1 = Y[:]
	X.sort()
	Y.sort()
	(min_x, min_y) = (X[2] - X[1], Y[2] - Y[1])
	sq = max(min_x, min_y)
	X_start = X[1]
	Y_start = Y[1]
	if X_start + sq > X[3]:
		X_start = X[3] - sq
	if Y_start + sq > Y[3]:
		Y_start = Y[3] - sq
	SQ = [(X_start, Y_start), (X_start + sq, Y_start), (X_start, Y_start + sq), (X_start + sq, Y_start + sq)]
	best = 10 ** 18
	ops = ['0123', '0132', '0213', '0231', '0312', '0321', '1023', '1032', '1203', '1230', '1302', '1320', '2013', '2031', '2103', '2130', '2301', '2310', '3012', '3021', '3102', '3120', '3201', '3210']
	Z = list(zip(X1, Y1))
	for op in ops:
		tmp = [SQ[int(s)] for s in op]
		curr = 0
		for i in range(4):
			(x, y) = Z[i]
			(a, b) = tmp[i]
			curr += abs(x - a) + abs(y - b)
		best = min(best, curr)
	return best
for _ in range(getInt()):
	print(solve())


import sys
input = sys.stdin.buffer.readline
from itertools import permutations

def prog():
	for _ in range(int(input())):
		ans = 10 ** 10
		points = []
		for i in range(4):
			(x, y) = map(int, input().split())
			points.append([x, y])
		for perm in permutations([0, 1, 2, 3]):
			if points[perm[0]][0] > points[perm[1]][0] or points[perm[2]][0] > points[perm[3]][0] or points[perm[0]][1] > points[perm[2]][1] or (points[perm[1]][1] > points[perm[3]][1]):
				continue
			amt_to_rectangle = abs(points[perm[1]][1] - points[perm[0]][1]) + abs(points[perm[3]][1] - points[perm[2]][1]) + abs(points[perm[2]][0] - points[perm[0]][0]) + abs(points[perm[3]][0] - points[perm[1]][0])
			wmax = max(points[perm[2]][1], points[perm[3]][1]) - min(points[perm[0]][1], points[perm[1]][1])
			lmax = max(points[perm[1]][0], points[perm[3]][0]) - min(points[perm[0]][0], points[perm[2]][0])
			wmin = max(0, min(points[perm[2]][1], points[perm[3]][1]) - max(points[perm[0]][1], points[perm[1]][1]))
			lmin = max(0, min(points[perm[1]][0], points[perm[3]][0]) - max(points[perm[0]][0], points[perm[2]][0]))
			if lmin > wmax:
				ans = min(ans, amt_to_rectangle + 2 * (lmin - wmax))
			elif wmin > lmax:
				ans = min(ans, amt_to_rectangle + 2 * (wmin - lmax))
			else:
				ans = min(ans, amt_to_rectangle)
		print(ans)
prog()


import itertools

def four_points(P):
	min_cost = 4 * int(1000000000.0)
	for p in itertools.permutations(range(4)):
		((ax, ay), (bx, by), (cx, cy), (dx, dy)) = (P[i] for i in p)
		x1 = (min(ax, bx), max(ax, bx))
		x2 = (min(cx, dx), max(cx, dx))
		cost = x1[1] - x1[0] + x2[1] - x2[0]
		y1 = (min(ay, cy), max(ay, cy))
		y2 = (min(by, dy), max(by, dy))
		cost += y1[1] - y1[0] + y2[1] - y2[0]
		x_seg = (max(x1[0] - x2[1], x2[0] - x1[1]), max(x1[1] - x2[0], x2[1] - x1[0]))
		y_seg = (max(y1[0] - y2[1], y2[0] - y1[1]), max(y1[1] - y2[0], y2[1] - y1[0]))
		cost += 2 * max(0, max(x_seg[0], y_seg[0]) - min(x_seg[1], y_seg[1]))
		min_cost = min(min_cost, cost)
	return min_cost
t = int(input())
for _ in range(t):
	P = [[int(xy) for xy in input().split()] for _ in range(4)]
	ans = four_points(P)
	print(ans)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]
MOD = 998244353
from itertools import permutations as pp

def solve():
	(X, Y) = ([], [])
	for i in range(4):
		(x, y) = getInts()
		X.append(x)
		Y.append(y)
	X_copy = X[:]
	Y_copy = Y[:]
	X.sort()
	Y.sort()
	if X[2] - X[1] < Y[2] - Y[1]:
		(X, Y, X_copy, Y_copy) = (Y[:], X[:], Y_copy[:], X_copy[:])
	L = X[2] - X[1]
	m = min(Y[1], Y[3] - L)
	sq = ((X[1], m), (X[2], m), (X[1], m + L), (X[2], m + L))
	ops = pp('0123')
	best = 10 ** 18
	for op in ops:
		tmp = [sq[int(op[j])] for j in range(4)]
		curr = 0
		for j in range(4):
			(x, y) = (X_copy[j], Y_copy[j])
			(a, b) = tmp[j]
			curr += abs(x - a) + abs(y - b)
		best = min(best, curr)
	return best
for _ in range(getInt()):
	print(solve())


sub_situation = [[0, 0], [0, 1], [1, 0], [1, 1]]

def absolute_solution(xy_list):
	min_answer = float('inf')
	for sub_s in sub_situation:
		x = xy_list[sub_s[0]]
		k = xy_list[2 + sub_s[1]] - x
		y_candidate = [xy_list[4], xy_list[5], xy_list[6] - k, xy_list[7] - k]
		y_candidate.sort()
		y = y_candidate[1]
		answer = abs(x - xy_list[0]) + abs(x - xy_list[1]) + abs(x + k - xy_list[2]) + abs(x + k - xy_list[3]) + abs(y - xy_list[4]) + abs(y - xy_list[5]) + abs(y + k - xy_list[6]) + abs(y + k - xy_list[7])
		min_answer = min(answer, min_answer)
	for sub_s in sub_situation:
		x = xy_list[sub_s[0]]
		y = xy_list[4 + sub_s[1]]
		k_candidate = [xy_list[2] - x, xy_list[3] - x, xy_list[6] - y, xy_list[7] - y]
		k_candidate.sort()
		k = k_candidate[1]
		answer = abs(x - xy_list[0]) + abs(x - xy_list[1]) + abs(x + k - xy_list[2]) + abs(x + k - xy_list[3]) + abs(y - xy_list[4]) + abs(y - xy_list[5]) + abs(y + k - xy_list[6]) + abs(y + k - xy_list[7])
		min_answer = min(answer, min_answer)
	for sub_s in sub_situation:
		x = xy_list[sub_s[0]]
		y_bias = xy_list[6 + sub_s[1]]
		y_candidate = [xy_list[4], xy_list[5], x + y_bias - xy_list[2], x + y_bias - xy_list[3]]
		y_candidate.sort()
		y = y_candidate[1]
		k = y_bias - y
		answer = abs(x - xy_list[0]) + abs(x - xy_list[1]) + abs(x + k - xy_list[2]) + abs(x + k - xy_list[3]) + abs(y - xy_list[4]) + abs(y - xy_list[5]) + abs(y + k - xy_list[6]) + abs(y + k - xy_list[7])
		min_answer = min(answer, min_answer)
	for sub_s in sub_situation:
		y = xy_list[4 + sub_s[0]]
		x_bias = xy_list[2 + sub_s[1]]
		x_candidate = [xy_list[0], xy_list[1], y + x_bias - xy_list[6], y + x_bias - xy_list[7]]
		x_candidate.sort()
		x = x_candidate[1]
		k = x_bias - x
		answer = abs(x - xy_list[0]) + abs(x - xy_list[1]) + abs(x + k - xy_list[2]) + abs(x + k - xy_list[3]) + abs(y - xy_list[4]) + abs(y - xy_list[5]) + abs(y + k - xy_list[6]) + abs(y + k - xy_list[7])
		min_answer = min(answer, min_answer)
	for sub_s in sub_situation:
		alpha = xy_list[2 + sub_s[0]]
		beta = xy_list[6 + sub_s[1]]
		y_candidate = [xy_list[4], xy_list[5], xy_list[0] + beta - alpha, xy_list[1] + beta - alpha]
		y_candidate.sort()
		y = y_candidate[1]
		x = y + alpha - beta
		k = xy_list[2] - x
		answer = abs(x - xy_list[0]) + abs(x - xy_list[1]) + abs(x + k - xy_list[2]) + abs(x + k - xy_list[3]) + abs(y - xy_list[4]) + abs(y - xy_list[5]) + abs(y + k - xy_list[6]) + abs(y + k - xy_list[7])
		min_answer = min(answer, min_answer)
	for sub_s in sub_situation:
		y = xy_list[4 + sub_s[0]]
		k = xy_list[6 + sub_s[1]] - y
		x_candidate = [xy_list[0], xy_list[1], xy_list[2] - k, xy_list[3] - k]
		x_candidate.sort()
		x = x_candidate[1]
		answer = abs(x - xy_list[0]) + abs(x - xy_list[1]) + abs(x + k - xy_list[2]) + abs(x + k - xy_list[3]) + abs(y - xy_list[4]) + abs(y - xy_list[5]) + abs(y + k - xy_list[6]) + abs(y + k - xy_list[7])
		min_answer = min(answer, min_answer)
	return min_answer

def set_xy_list(point_list, order):
	if point_list[order[0]][0] > point_list[order[3]][0] or point_list[order[1]][0] > point_list[order[2]][0] or point_list[order[0]][1] > point_list[order[1]][1] or (point_list[order[3]][1] > point_list[order[2]][1]):
		return []
	xy_list = [point_list[order[0]][0], point_list[order[1]][0], point_list[order[2]][0], point_list[order[3]][0], point_list[order[0]][1], point_list[order[3]][1], point_list[order[2]][1], point_list[order[1]][1]]
	return xy_list

def solution(point_list):
	min_answer = float('inf')
	order = [0, 1, 2, 3]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [0, 1, 3, 2]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [0, 2, 1, 3]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [0, 2, 3, 1]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [0, 3, 1, 2]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [0, 3, 2, 1]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [1, 0, 2, 3]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [1, 0, 3, 2]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [1, 2, 0, 3]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [1, 2, 3, 0]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [1, 3, 2, 0]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [1, 3, 0, 2]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [2, 0, 1, 3]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [2, 0, 3, 1]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [2, 1, 0, 3]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [2, 1, 3, 0]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [2, 3, 1, 0]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [2, 3, 0, 1]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [3, 2, 1, 0]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [3, 2, 0, 1]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [3, 1, 0, 2]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [3, 1, 2, 0]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [3, 0, 1, 2]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	order = [3, 0, 2, 1]
	xy_list = set_xy_list(point_list, order)
	if xy_list:
		min_answer = min(absolute_solution(xy_list), min_answer)
	return min_answer
import sys
T = int(sys.stdin.readline().strip())
while T > 0:
	T -= 1
	point_list = []
	for i in range(4):
		(x, y) = sys.stdin.readline().strip().split(' ')
		point_list.append([int(x), int(y)])
	print(solution(point_list))


import sys, os, io
input = sys.stdin.readline
T = int(input())
ans = [0] * T
for t in range(T):
	(X, Y) = ([0] * 4, [0] * 4)
	A = [0] * 4
	for i in range(4):
		(X[i], Y[i]) = map(int, input().split())
		A[i] = [X[i], Y[i]]
	X.sort()
	Y.sort()
	A.sort()
	cnt = 0
	for i in range(2):
		rank = 1
		for j in range(4):
			if A[i][1] < A[j][1]:
				rank += 1
		if rank <= 2:
			cnt += 1
	if cnt != 1:
		ans[t] += min(Y[2] - Y[1], X[2] - X[1]) * 2
	x_min = X[2] - X[1]
	x_max = X[3] - X[0]
	y_min = Y[2] - Y[1]
	y_max = Y[3] - Y[0]
	if not (x_max < y_min or y_max < x_min):
		ans[t] += X[3] - X[2] + (X[1] - X[0])
		ans[t] += Y[3] - Y[2] + (Y[1] - Y[0])
	elif x_max < y_min:
		ans[t] += X[3] - X[2] + (X[1] - X[0])
		ans[t] += Y[3] - Y[2] + (Y[1] - Y[0]) + 2 * (y_min - x_max)
	else:
		ans[t] += X[3] - X[2] + (X[1] - X[0]) + 2 * (x_min - y_max)
		ans[t] += Y[3] - Y[2] + (Y[1] - Y[0])
print(*ans, sep='\n')


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16

def cal(xy):
	res = inf
	for _ in range(2):
		xy.sort()
		for i in [0, 2]:
			if xy[i][1] > xy[i + 1][1]:
				(xy[i], xy[i + 1]) = (xy[i + 1], xy[i])
		xmax = max(xy[2][0], xy[3][0]) - min(xy[1][0], xy[0][0])
		xmin = min(xy[2][0], xy[3][0]) - max(xy[1][0], xy[0][0])
		ymax = max(xy[1][1], xy[3][1]) - min(xy[0][1], xy[2][1])
		ymin = min(xy[1][1], xy[3][1]) - max(xy[0][1], xy[2][1])
		cur = max(max(ymin, xmin) - min(xmax, ymax), 0) * 2 + abs(xy[0][0] - xy[1][0]) + abs(xy[2][0] - xy[3][0]) + abs(xy[0][1] - xy[2][1]) + abs(xy[1][1] - xy[3][1])
		res = min(res, cur)
		xy = [[y, x] for (x, y) in xy]
	return res
for t in range(II()):
	xy = LLI(4)
	ans = cal(xy)
	print(ans)


import math
sorts = [[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]

def solve(ps):
	res = 10000000000
	for i in range(len(sorts)):
		move = 0
		(lb_x, lb_y) = ps[sorts[i][0]]
		(lt_x, lt_y) = ps[sorts[i][1]]
		(rb_x, rb_y) = ps[sorts[i][2]]
		(rt_x, rt_y) = ps[sorts[i][3]]
		if max([rb_x, rt_x]) < min([lb_x, lt_x]):
			x_move = lb_x + lt_x - rb_x - rt_x
			x_side = [0, 0]
		else:
			x_move = abs(lb_x - lt_x) + abs(rb_x - rt_x)
			x_side = [min([rb_x, rt_x]) - max([lb_x, lt_x]), max([rb_x, rt_x]) - min([lb_x, lt_x])]
		if max([lt_y, rt_y]) < min([lb_y, rb_y]):
			y_move = lb_y + rb_y - lt_y - rt_y
			y_side = [0, 0]
		else:
			y_move = abs(lb_y - rb_y) + abs(lt_y - rt_y)
			y_side = [min([lt_y, rt_y]) - max([lb_y, rb_y]), max([lt_y, rt_y]) - min([lb_y, rb_y])]
		if x_side[0] > y_side[1]:
			move = x_move + y_move + 2 * (x_side[0] - y_side[1])
		elif y_side[0] > x_side[1]:
			move = x_move + y_move + 2 * (y_side[0] - x_side[1])
		else:
			move = x_move + y_move
		if res > move:
			res = move
	return res
t = int(input().strip())
for _ in range(t):
	ps = []
	for _ in range(4):
		ps.append([int(x) for x in input().strip().split(' ')])
	print(solve(ps))


def read_int():
	return int(input())

def read_ints():
	return map(int, input().split(' '))

def solve(x, y):
	xcost = x[1] - x[0] + x[3] - x[2]
	ycost = y[1] - y[0] + y[3] - y[2]
	xlo = max(0, x[2] - x[1])
	xhi = x[3] - x[0]
	ylo = max(0, y[2] - y[1])
	yhi = y[3] - y[0]
	ans = xcost + ycost
	if ylo > xhi:
		ans += 2 * (ylo - xhi)
	elif xlo > yhi:
		ans += 2 * (xlo - yhi)
	return ans
t = read_int()
for case_num in range(t):
	x = []
	y = []
	for i in range(4):
		(xi, yi) = read_ints()
		x.append((xi, i))
		y.append((yi, i))
	x.sort()
	y.sort()
	xl = set([x[0][1], x[1][1]])
	yl = set([y[0][1], y[1][1]])
	ans = int(1e+18)
	if len(xl.intersection(yl)) != 1:
		ans = min(solve([x[0][0], x[2][0], x[1][0], x[3][0]], [y[0][0], y[1][0], y[2][0], y[3][0]]), solve([x[0][0], x[1][0], x[2][0], x[3][0]], [y[0][0], y[2][0], y[1][0], y[3][0]]))
	else:
		ans = solve([x[0][0], x[1][0], x[2][0], x[3][0]], [y[0][0], y[1][0], y[2][0], y[3][0]])
	print(ans)


import os
from io import BytesIO
import math
import itertools

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

def main():
	t = int(input())
	out = []
	for _ in range(t):
		p = []
		for i in range(4):
			p.append(list(map(int, input().split())))
		xmin = xmax = p[0][0]
		ymin = ymax = p[0][1]
		for i in range(4):
			xmin = min(xmin, p[i][0])
			xmax = max(xmax, p[i][0])
			ymin = min(ymin, p[i][1])
			ymax = max(ymax, p[i][1])
		dx = xmax - xmin
		dy = ymax - ymin
		side = min(dx, dy)
		ind = 1
		if dy < dx:
			ind = 0
		a = sorted([p[i][ind] for i in range(4)])
		third = a[-3]
		if dx <= dy:
			top = min(ymax, third + side)
			sq = [[xmin, top], [xmin, top - side], [xmax, top], [xmax, top - side]]
		else:
			top = min(xmax, third + side)
			sq = [[top, ymin], [top - side, ymin], [top, ymax], [top - side, ymax]]
		best = math.inf
		for x in list(itertools.permutations([0, 1, 2, 3])):
			cur = dist(p[0], sq[x[0]])
			cur += dist(p[1], sq[x[1]])
			cur += dist(p[2], sq[x[2]])
			cur += dist(p[3], sq[x[3]])
			if cur < best:
				best = cur
		out.append(best)
	print('\n'.join(map(str, out)))
main()


import sys
input = sys.stdin.readline
from itertools import permutations

def fx(a, b, c, d):
	return (min(b, c) - max(a, d), max(b, c) - min(a, d), abs(b - c) + abs(a - d))
(T,) = map(int, input().split())
for _ in range(T):
	X = []
	for _ in range(4):
		(x, y) = map(int, input().split())
		X.append((x, y))
	R = 10 ** 18
	for pp in permutations(list(range(4)), 4):
		((ax, ay), (bx, by), (cx, cy), (dx, dy)) = [X[p] for p in pp]
		(k1, k2, ll) = fx(ax, bx, cx, dx)
		(k3, k4, llb) = fx(ay, cy, dy, by)
		for k in [k1, k2, k3, k4, 0]:
			if k < 0:
				continue
			xx = ll + 2 * max(k - k2, k1 - k, 0)
			yy = llb + 2 * max(k - k4, k3 - k, 0)
			R = min(R, xx + yy)
	print(R)


from itertools import permutations

def make_f(ka, kb, lx):

	def _g(t):
		return max(lx, lx + 2 * (t - kb), lx + 2 * (ka - t))
	return _g

def fx(a, b, c, d):
	k1 = min(b, c) - max(a, d)
	k2 = max(b, c) - min(a, d)
	ll = abs(b - c) + abs(a - d)
	return (k1, k2, ll)

def ff(x):
	((ax, ay), (bx, by), (cx, cy), (dx, dy)) = x
	(k1, k2, ll) = fx(ax, bx, cx, dx)
	(k3, k4, llb) = fx(ay, cy, dy, by)
	fa = make_f(k1, k2, ll)
	fb = make_f(k3, k4, llb)
	R = 10 ** 18
	mx = -1
	for k in [k1, k2, k3, k4, 0]:
		if k < 0:
			continue
		R = min(R, fa(k) + fb(k))
	return R
(T,) = map(int, input().split())
for _ in range(T):
	X = []
	for _ in range(4):
		(x, y) = map(int, input().split())
		X.append((x, y))
	R = 10 ** 18
	for pp in permutations(list(range(4)), 4):
		Y = []
		for pi in pp:
			Y.append(X[pi])
		R = min(R, ff(Y))
	print(R)


import itertools
cnt_case = int(input())
index = [0, 1, 2, 3]
a = [[0 for x in range(2)] for y in range(4)]
di = [0] * 100000
x = [0, 0, 0, 0]
y = [0, 0, 0, 0]
indexs = list(itertools.permutations(index, len(index)))
for i in range(len(indexs)):
	indexs[i] = list(indexs[i])
for i in range(cnt_case):
	res = 1000000000000
	cnt = 0
	for i in range(4):
		(a[i][0], a[i][1]) = [int(_v) for _v in input().split(' ')]
		for j in range(i):
			di[cnt] = abs(a[i][0] - a[j][0])
			cnt += 1
			di[cnt] = abs(a[i][1] - a[j][1])
			cnt += 1
	for _ind in indexs:
		for i in range(cnt):
			tmp_res = 0
			for k in range(4):
				(x[k], y[k]) = (a[_ind[k]][0], a[_ind[k]][1])
			x[2] -= di[i]
			x[3] -= di[i]
			y[1] -= di[i]
			y[2] -= di[i]
			x = sorted(x)
			y = sorted(y)
			for i in range(4):
				tmp_res += abs(x[i] - x[2]) + abs(y[i] - y[2])
			res = min(res, tmp_res)
	print(res)


import sys
from itertools import permutations

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	for t in range(mint()):
		pos = [tuple(mints()) for i in range(4)]
		res = int(9e+18)
		qwe = []
		for i in range(4):
			for j in range(i):
				qwe.append(abs(pos[i][0] - pos[j][0]))
				qwe.append(abs(pos[i][1] - pos[j][1]))
		per = list(permutations(pos))
		for z in per:
			for w in qwe:
				posx = [z[0][0], z[1][0], z[2][0] + w, z[3][0] + w]
				posy = [z[0][1], z[1][1] + w, z[2][1], z[3][1] + w]
				posx.sort()
				posy.sort()
				x = posx[1]
				y = posy[1]
				xsum = sum([abs(i - x) for i in posx])
				ysum = sum([abs(i - y) for i in posy])
				res = min(res, xsum + ysum)
		print(res)
solve()


import sys
rl = []

def gen_sort(n, x):
	if n == 0:
		rl.append(x[:])
	for i in range(4):
		if i in x:
			continue
		x.append(i)
		gen_sort(n - 1, x)
		x.pop()
	return
gen_sort(4, [])

def calc(p):
	xlr = [min(p[0][0], p[2][0]), max(p[0][0], p[2][0])]
	xrr = [min(p[1][0], p[3][0]), max(p[1][0], p[3][0])]
	dxr = [abs(xrr[0] - xlr[1]), abs(xrr[1] - xlr[0])]
	if dxr[0] > dxr[1]:
		(dxr[0], dxr[1]) = (dxr[1], dxr[0])
	y_up_r = [min(p[0][1], p[1][1]), max(p[0][1], p[0][1])]
	y_down_r = [min(p[2][1], p[3][1]), max(p[2][1], p[3][1])]
	dyr = [abs(y_down_r[0] - y_up_r[1]), abs(y_down_r[1] - y_up_r[0])]
	if dyr[0] > dyr[1]:
		(dyr[1], dyr[0]) = (dyr[0], dyr[1])
	ans = abs(p[2][0] - p[0][0]) + abs(p[1][0] - p[3][0]) + abs(p[1][1] - p[0][1]) + abs(p[2][1] - p[3][1])
	if dxr[1] < dyr[0]:
		ans += (dyr[0] - dxr[1]) * 2
	elif dyr[1] < dxr[0]:
		ans += (dxr[0] - dyr[1]) * 2
	return ans
T = int(sys.stdin.readline().strip())
while T > 0:
	T -= 1
	point = []
	for i in range(4):
		(a, b) = sys.stdin.readline().strip().split(' ')
		point.append([int(a), int(b)])
	res = 4000000000
	for now in rl:
		p = []
		for i in range(4):
			p.append(point[now[i]])
		tmp = calc(p)
		res = min(res, tmp)
	print(res)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	from itertools import permutations
	t = int(input())
	ans = ['0'] * t

	def calc(points, x1, y1, x2, y2):
		return abs(points[0][0] - x1) + abs(points[0][1] - y1) + abs(points[1][0] - x2) + abs(points[1][1] - y1) + abs(points[2][0] - x1) + abs(points[2][1] - y2) + abs(points[3][0] - x2) + abs(points[3][1] - y2)
	eps = 1e-08
	for ti in range(t):
		points = [tuple(map(float, input().split())) for _ in range(4)]
		x_set = sorted(set((x for (x, _) in points)))
		y_set = sorted(set((y for (_, y) in points)))
		perm = tuple(permutations(points))
		res = min((calc(points, points[i][0], points[i][1], points[i][0], points[i][1]) for i in range(4)))
		for pts in perm:
			for (i, x1) in enumerate(x_set):
				for x2 in x_set[i + 1:]:
					cost = abs(pts[0][0] - x1) + abs(pts[1][0] - x2) + abs(pts[2][0] - x1) + abs(pts[3][0] - x2)
					if cost >= res:
						continue
					for y1 in y_set:
						for y2 in (y1 - (x2 - x1), y1 + (x2 - x1)):
							res = min(res, cost + abs(pts[0][1] - y1) + abs(pts[1][1] - y1) + abs(pts[2][1] - y2) + abs(pts[3][1] - y2))
			for (i, y1) in enumerate(y_set):
				for y2 in y_set[i + 1:]:
					cost = abs(pts[0][1] - y1) + abs(pts[1][1] - y2) + abs(pts[2][1] - y1) + abs(pts[3][1] - y2)
					if cost >= res:
						continue
					for x1 in x_set:
						for x2 in (x1 - (y2 - y1), x1 + (y2 - y1)):
							res = min(res, cost + abs(pts[0][0] - x1) + abs(pts[1][0] - x1) + abs(pts[2][0] - x2) + abs(pts[3][0] - x2))
		ans[ti] = str(int(res + eps))
	sys.stdout.buffer.write(('\n'.join(ans) + '\n').encode('utf-8'))
main()


import itertools
for t in range(int(input())):
	(points, sides, ans) = ([], [0], -1)
	for i in range(4):
		points.append([int(v) for v in input().split(' ')])
	for i in range(0, 3):
		for j in range(i + 1, 4):
			sides.append(abs(points[i][0] - points[j][0]))
			sides.append(abs(points[i][1] - points[j][1]))
	for point in itertools.permutations(points, 4):
		(x1, x2) = (min(point[0][0], point[2][0]), max(point[0][0], point[2][0]))
		(x3, x4) = (min(point[1][0], point[3][0]), max(point[1][0], point[3][0]))
		(y1, y2) = (min(point[0][1], point[1][1]), max(point[0][1], point[1][1]))
		(y3, y4) = (min(point[2][1], point[3][1]), max(point[2][1], point[3][1]))
		(side_x_l, side_x_r) = (x3 - x2, x4 - x1)
		(side_y_l, side_y_r) = (y3 - y2, y4 - y1)
		if side_y_r < 0 or side_x_r < 0:
			continue
		if side_x_l < 0:
			side_x_l = 0
		if side_y_l < 0:
			side_y_l = 0
		count_temp = x2 - x1 + x4 - x3 + y2 - y1 + y4 - y3
		for side in set(sides):
			count = count_temp
			if side_x_l > side or side_x_r < side:
				count += min(abs(side - side_x_l), abs(side - side_x_r)) * 2
			if side_y_l > side or side_y_r < side:
				count += min(abs(side - side_y_l), abs(side - side_y_r)) * 2
			if ans == -1 or count < ans:
				ans = count
	print(ans)