Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given N *distinct* points in a 2-D plane, numbered 1 through N. The X-coordinate of the points are X_{1}, X_{2}, \ldots, X_{N} respectively and the Y-coordinates are Y_{1}, Y_{2}, \ldots, Y_{N} respectively. Your goal is to make the location of all the N points equal to that of each other. To achieve this, you can do some operations.

In one operation, you choose an index i\;(1 ≤ i ≤ N) and a real number K and change the location of the i^{th} point in one of the following ways:
Set (X_{i}, Y_{i}) = (X_{i} + K, Y_{i})
Set (X_{i}, Y_{i}) = (X_{i}, Y_{i} + K)
Set (X_{i}, Y_{i}) = (X_{i} + K, Y_{i} + K)
Set (X_{i}, Y_{i}) = (X_{i} + K, Y_{i} - K)

Find the minimum number of operations to achieve the goal.

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- Each test case contains three lines of input.
- The first line contains a single integer N.
- The second line contains N space-separated integers X_{1}, X_{2}, \ldots, X_{N}.
- The third line contains N space-separated integers Y_{1}, Y_{2}, \ldots, Y_{N}.

------ Output Format ------ 

For each test case, print a single line containing one integer - the minimum number of operations to achieve the goal.

------ Constraints ------ 

$1 ≤ T ≤ 300$
$2 ≤ N ≤ 100$
$-10^{9} ≤ X_{i}, Y_{i} ≤ 10^{9}$
$(X_{i}, Y_{i}) \neq (X_{j}, Y_{j})$ if $(i \neq j)$
- Sum of $N$ over all test cases does not exceed $600$.

------ subtasks ------ 

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
2
3
0 1 -4
0 1 5
3
0 1 3
1 1 -1

----- Sample Output 1 ------ 
3
2

----- explanation 1 ------ 
Test case $1$ :  
- In the first operation, you choose $i = 2$, and $K = - 1$ and apply the third type of operation. So the location of $2^{nd}$ point becomes $(1 - 1, 1 - 1) = (0, 0)$.

- In the second operation, you choose $i = 3$, and $K = 4$ and apply the first type of operation. So the location of $3^{rd}$ point becomes $(- 4 + 4, 5) = (0, 5)$.

- In the third operation, you choose $i = 3$, and $K = -5$ and apply the second type of operation. So the location of $3^{rd}$ point becomes $(0, 5 - 5) = (0, 0)$.

Hence after the above operations, the location of the given three points becomes equal to each other.

Test case $2$ : 
- In the first operation, you choose $i = 1$ and $K = 1$ and apply the first type of operation. So the location of 1st point becomes $(0 + 1, 1) = (1, 1)$.

- In the second operation, you choose $i = 3$, and $K = -2$ and apply the fourth type of operation. So the location of 3rd point becomes $(3 - 2, -1 - (-2)) = (1, 1)$.

Hence after the above operations, the location of the given three points becomes equal to each other.

Difficulty: HARD
Tags: Geometry

Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
from collections import namedtuple, defaultdict
from math import isclose, floor, ceil
line = namedtuple('line', ['m', 'c'])

def intersection(l1: line, l2: line):
	if l1.m == l2.m:
		return None
	elif l1.m == 'inf':
		return (l1.c, l2.m * l1.c + l2.c)
	elif l2.m == 'inf':
		return (l2.c, l1.m * l2.c + l1.c)
	x = (l2.c - l1.c) / (l1.m - l2.m)
	return (x, l1.m * x + l1.c)

def intgen():
	return (int(x) for x in input().split())

def closer(p):
	if isclose(p, floor(p)):
		return int(floor(p))
	elif isclose(p, ceil(p)):
		return int(ceil(p))
	return None
testcases = int(input())
for testcase in range(testcases):
	(n, xs, ys) = (int(input()), list(intgen()), list(intgen()))
	points = list(zip(xs, ys))
	linecount = defaultdict(int)
	for (x, y) in points:
		linecount[line(0, y)] += 1
		linecount[line('inf', x)] += 1
		linecount[line(1, y - x)] += 1
		linecount[line(-1, x + y)] += 1
	(lines, ln, ls) = (list(linecount.keys()), len(linecount), set())
	for j in range(ln):
		for k in range(j + 1, ln):
			if lines[j].m != lines[k].m:
				(x, y) = intersection(lines[j], lines[k])
				u = linecount[line(0, closer(y))] + linecount[line('inf', closer(x))] + linecount[line(1, closer(y - x))] + linecount[line(-1, closer(y + x))]
				if (closer(x), closer(y)) in points:
					u -= 4
					ls.add(u + 2 * (n - 1 - u))
				else:
					ls.add(u + 2 * (n - u))
	print(min(ls))


import math
t = int(input())

def find_xy(m1, m2, x1, x2, y1, y2):
	(a1, b1) = (m1[0], m1[1])
	(a2, b2) = (m2[0], m2[1])
	c1 = a1 * x1 + b1 * y1
	c2 = a2 * x2 + b2 * y2
	Dx = c1 * b2 - c2 * b1
	Dy = a1 * c2 - a2 * c1
	D = a1 * b2 - a2 * b1
	x = Dx / D
	y = Dy / D
	return (x, y)
for _ in range(t):
	n = int(input())
	X = list(map(float, input().split()))
	Y = list(map(float, input().split()))
	m = [[1, 1], [1, -1], [0, 1], [1, 0]]
	adict = {}
	for i in range(n - 1):
		for j in range(i + 1, n):
			x = abs(X[i] - X[j])
			y = abs(Y[i] - Y[j])
			checker = set()
			for m1 in m:
				for m2 in m:
					if m1 != m2:
						temp = find_xy(m1, m2, X[i], X[j], Y[i], Y[j])
						checker.add(temp)
			for temp in checker:
				try:
					adict[temp[0], temp[1]] += 1
				except:
					adict[temp[0], temp[1]] = 1
	res = []
	remains = {}
	for i in range(n):
		dist = 0
		for j in range(n):
			if i != j:
				x = abs(X[i] - X[j])
				y = abs(Y[i] - Y[j])
				if x == 0 or y == 0 or x == y:
					dist += 1
					remains[X[i], Y[i]] = 0
				else:
					dist += 2
		res.append(dist)
	keys = list(adict.keys())
	key2 = list(remains.keys())
	for i in range(len(keys)):
		reserve = {}
		if adict[keys[i]] == 1:
			continue
		for j in range(len(remains)):
			try:
				m0 = (key2[j][1] - keys[i][1]) / (key2[j][0] - keys[i][0])
				if m0 == 0 or m0 == -1 or m0 == 1:
					try:
						reserve[m0] += 1
					except:
						reserve[m0] = 1
			except:
				m0 = 'inf'
				try:
					reserve[m0] += 1
				except:
					reserve[m0] = 1
		for t0 in range(len(reserve)):
			key0 = list(reserve.keys())
			t1 = reserve[key0[t0]]
			t1 = t1 * (t1 - 1) / 2
			adict[keys[i]] += t1
	for i in range(len(keys)):
		tem = 1 + math.sqrt(1 + 8 * adict[keys[i]])
		tem /= 2
		dist = tem + (n - tem) * 2
		res.append(dist)
		if int(dist) == 1:
			print(adict[keys[i]])
	print(int(min(res)))


import sys
for t in range(int(input())):
	N = int(input())
	x_ = list(map(int, input().split()))
	y_ = list(map(int, input().split()))
	ope_max = int(sys.maxsize)
	x = 0
	y = 0
	m = 1
	if N < 50:
		m = 4
	for k in range(m):
		for p in range(N):
			for q in range(N):
				if k == 0:
					x = x_[p]
					y = y_[q]
				elif k == 1:
					x = y_[p] + x_[q] - y_[q]
					y = y_[p]
				elif k == 2:
					x = (x_[q] + y_[q] + x_[p] - y_[p]) / 2.0
					y = x + y_[p] - x_[p]
				elif k == 3:
					x = x_[p] + y_[p] - y_[q]
					y = y_[q]
				operations = 0
				for j in range(N):
					if x == x_[j] and y == y_[j]:
						operations += 0
					elif abs(x - x_[j]) == abs(y - y_[j]) or x == x_[j] or y == y_[j]:
						operations += 1
					else:
						operations += 2
				if ope_max > operations:
					ope_max = operations
	print(ope_max)


def check(h, k, x, y, n):
	count = 0
	for j in range(n):
		if h == x[j] and k == y[j]:
			count += 0
		elif abs(h - x[j]) == abs(k - y[j]) or h == x[j] or k == y[j]:
			count += 1
		else:
			count += 2
	return count
for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split(' ')))
	y = list(map(int, input().split(' ')))
	min_step = 10 ** 100
	h = 0
	k = 0
	m = 1
	if n < 50:
		m = 4
	for l in range(m):
		for t in range(n):
			for s in range(n):
				if l == 0:
					h = x[t]
					k = y[s]
				elif l == 1:
					h = y[t] + x[s] - y[s]
					k = y[t]
				elif l == 2:
					h = (x[s] + y[s] + x[t] - y[t]) / 2
					k = h + y[t] - x[t]
				elif l == 3:
					h = x[t] + y[t] - y[s]
					k = y[s]
				mini = check(h, k, x, y, n)
				min_step = min(min_step, mini)
	print(min_step)


def calci(Ox, Oy):
	step = 0
	for j in range(N):
		K1 = Ox - X[j]
		if X[j] == Ox and Y[j] == Oy:
			continue
		elif X[j] + K1 == Ox and Y[j] + K1 == Oy:
			step = step + 1
		elif X[j] == Ox:
			step = step + 1
		elif Y[j] == Oy:
			step = step + 1
		elif X[j] + K1 == Ox and Y[j] - K1 == Oy:
			step = step + 1
		else:
			step = step + 2
	min.append(step)
	min.sort()

def calculate(x, y):
	if (x, y) in d:
		d[x, y] = d[x, y] + 1
	else:
		d[x, y] = 1
T = int(input())
for i in range(T):
	N = int(input())
	X = input().split()
	Y = input().split()
	d = {}
	min = []
	for i in range(N):
		X[i] = int(X[i])
		Y[i] = int(Y[i])
	for i in range(N):
		Ox = X[i]
		Oy = Y[i]
		step = 0
		for j in range(N):
			K1 = Ox - X[j]
			if X[j] == Ox and Y[j] == Oy:
				continue
			elif X[j] + K1 == Ox and Y[j] + K1 == Oy:
				step = step + 1
			elif X[j] == Ox:
				step = step + 1
			elif Y[j] == Oy:
				step = step + 1
			elif X[j] + K1 == Ox and Y[j] - K1 == Oy:
				step = step + 1
			else:
				step = step + 2
		min.append(step)
	min.sort()
	for i in range(N):
		for j in range(i + 1, N):
			if X[i] + Y[i] == X[j] + Y[j] or X[i] - Y[i] == X[j] - Y[j] or X[i] == X[j] or (Y[i] == Y[j]):
				calculate(X[i], Y[i])
				calculate(X[j], Y[j])
			else:
				calculate((X[i] + Y[i] + X[j] - Y[j]) / 2, (X[i] + Y[i] - X[j] + Y[j]) / 2)
				calculate(X[j], X[i] + Y[i] - X[j])
				calculate(X[i] + Y[i] - Y[j], Y[j])
				calculate((X[i] - Y[i] + X[j] + Y[j]) / 2, (-X[i] + Y[i] + X[j] + Y[j]) / 2)
				calculate(X[j], -X[i] + Y[i] + X[j])
				calculate(X[i] - Y[i] + Y[j], Y[j])
				calculate(X[i], X[j] + Y[j] - X[i])
				calculate(X[i], -X[j] + Y[j] + X[i])
				calculate(X[i], Y[j])
				calculate(X[j] + Y[j] - Y[i], Y[i])
				calculate(X[j] - Y[j] + Y[i], Y[i])
				calculate(X[j], Y[i])
	max = 0
	for i in d:
		if d[i] > max:
			max = d[i]
			point = i
	calci(point[0], point[1])
	print(min[0])


from collections import defaultdict
from itertools import product

def f(l1, l2):
	(a1, b1, c1) = l1
	(a2, b2, c2) = l2
	det = a1 * b2 - a2 * b1
	det1 = c1 * b2 - c2 * b1
	det2 = a1 * c2 - a2 * c1
	return (det1 / det, det2 / det)

def f1(l, s):
	if len(l) == 4:
		l = l[:3]
	elif len(l) == 7:
		l = l[:4]
	return sum(l) - s
for t in range(int(input())):
	n = int(input())
	(d1, d2, d3, d4) = (defaultdict(set), defaultdict(set), defaultdict(set), defaultdict(set))
	for (x, y) in zip(map(float, input().split()), map(float, input().split())):
		d1[1, 0, x].add((x, y))
		d2[0, 1, y].add((x, y))
		d3[-1, 1, y - x].add((x, y))
		d4[1, 1, x + y].add((x, y))
	d = {}
	for (dct1, dct2) in ((d1, d2), (d1, d3), (d1, d4), (d2, d3), (d2, d4), (d3, d4)):
		for (l1, l2) in product(dct1, dct2):
			intersec = f(l1, l2)
			if intersec in d:
				d[intersec][0].append(len(dct2[l2]))
				if intersec in dct2[l2]:
					d[intersec][1] = 2
			else:
				d[intersec] = [[len(dct1[l1]), len(dct2[l2])], 2 * (intersec in dct2[l2])]
	print(2 * n - max((f1(*el) for el in d.values())))


import sys

def check(h, k, x, y, n):
	count = 0
	for j in range(n):
		if h == x[j] and k == y[j]:
			count += 0
		elif abs(h - x[j]) == abs(k - y[j]) or h == x[j] or k == y[j]:
			count += 1
		else:
			count += 2
	return count
num = int(input())
for i in range(num):
	n = int(input())
	x = list(map(int, input().split(' ')))
	y = list(map(int, input().split(' ')))
	min_step = int(sys.maxsize)
	h = 0
	k = 0
	m = 1
	if n < 50:
		m = 4
	for l in range(m):
		for t in range(n):
			for s in range(n):
				if l == 0:
					h = x[t]
					k = y[s]
				elif l == 1:
					h = y[t] + x[s] - y[s]
					k = y[t]
				elif l == 2:
					h = (x[s] + y[s] + x[t] - y[t]) / 2.0
					k = h + y[t] - x[t]
				elif l == 3:
					h = x[t] + y[t] - y[s]
					k = y[s]
				mini = check(h, k, x, y, n)
				if min_step > mini:
					min_step = mini
	print(min_step)


for _ in range(int(input())):
	N = int(input())
	X = list(map(int, input().split()))
	Y = list(map(int, input().split()))
	setP = set()
	for i in range(N):
		setP.add((X[i], Y[i]))
	left = {}
	right = {}
	sY = {}
	sX = {}
	for i in range(N):
		l = X[i] + Y[i]
		left[l] = left.get(l, 0) + 1
		r = X[i] - Y[i]
		right[r] = right.get(r, 0) + 1
		sX[X[i]] = sX.get(X[i], 0) + 1
		sY[Y[i]] = sY.get(Y[i], 0) + 1
	minC = 10 ** 5
	for (x1, y1) in left.items():
		for (x2, y2) in right.items():
			x = (x1 + x2) / 2
			y = (x1 - x2) / 2
			count = y1 + y2 + sY.get(y, 0) + sX.get(x, 0)
			if (x, y) in setP:
				count -= 4
				count += max(0, 2 * (N - count - 1))
			else:
				count += max(0, 2 * (N - count))
			minC = min(minC, count)
	for (x, nx) in sX.items():
		for (y, ny) in sY.items():
			count = nx + ny + left.get(y + x, 0) + right.get(x - y, 0)
			if (x, y) in setP:
				count -= 4
				count += max(0, 2 * (N - count - 1))
			else:
				count += max(0, 2 * (N - count))
			minC = min(minC, count)
	for (x, nx) in sX.items():
		for (s, ns) in left.items():
			y = s - x
			count = nx + ns + right.get(x - y, 0) + sY.get(y, 0)
			if (x, y) in setP:
				count -= 4
				count += max(0, 2 * (N - count - 1))
			else:
				count += max(0, 2 * (N - count))
			minC = min(minC, count)
	for (x, nx) in sX.items():
		for (d, nd) in right.items():
			y = x - d
			count = nx + nd + left.get(x + y, 0) + sY.get(y, 0)
			if (x, y) in setP:
				count -= 4
				count += max(0, 2 * (N - count - 1))
			else:
				count += max(0, 2 * (N - count))
			minC = min(minC, count)
	for (y, ny) in sY.items():
		for (s, ns) in left.items():
			x = s - y
			count = ny + ns + right.get(x - y, 0) + sX.get(x, 0)
			if (x, y) in setP:
				count -= 4
				count += max(0, 2 * (N - count - 1))
			else:
				count += max(0, 2 * (N - count))
			minC = min(minC, count)
	for (y, ny) in sY.items():
		for (d, nd) in right.items():
			x = d + y
			count = ny + nd + left.get(x + y, 0) + sX.get(x, 0)
			if (x, y) in setP:
				count -= 4
				count += max(0, 2 * (N - count - 1))
			else:
				count += max(0, 2 * (N - count))
			minC = min(minC, count)
	print(minC)


import sys
from collections import Counter

def rall():
	return sys.stdin.readlines()

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

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
NT = int(rl())
for ti in range(NT):
	_ = rl()
	xs = [int(x) for x in rl().split(' ')]
	ys = [int(x) for x in rl().split(' ')]
	n = len(xs)
	points = set(zip(xs, ys))
	freq_x = Counter(xs)
	freq_y = Counter(ys)
	freq_xpy = Counter([xs[i] + ys[i] for i in range(n)])
	freq_xmy = Counter([xs[i] - ys[i] for i in range(n)])

	def tot_move_cost(points, ix, iy):
		tot_cost = 0
		for (px, py) in points:
			if px == ix and py == iy:
				tot_cost += 0
			elif px == ix or py == iy or px + py == ix + iy or (px - py == ix - iy):
				tot_cost += 1
			else:
				tot_cost += 2
		return tot_cost

	def tot_cost_to(ix, iy):
		(n_samex, n_samey) = (freq_x[ix], freq_y[iy])
		(n_xpy, n_xmy) = (freq_xpy[ix + iy], freq_xmy[ix - iy])
		n_rem = n - (n_samex + n_samey + n_xpy + n_xmy)
		if (ix, iy) in points:
			n_samex -= 1
			n_samey -= 1
			n_xpy -= 1
			n_xmy -= 1
			n_rem += 4 - 1
		return n_samex + n_samey + n_xpy + n_xmy + 2 * n_rem
	all_cands = {}
	intersections = set()
	mn = float('inf')
	for ix in freq_x:
		for iy in freq_y:
			mn = min(mn, tot_cost_to(ix, iy))
	for ix in freq_x:
		for xpy in freq_xpy:
			iy = xpy - ix
			mn = min(mn, tot_cost_to(ix, iy))
	for ix in freq_x:
		for xmy in freq_xmy:
			iy = ix - xmy
			mn = min(mn, tot_cost_to(ix, iy))
	for iy in freq_y:
		for xpy in freq_xpy:
			ix = xpy - iy
			mn = min(mn, tot_cost_to(ix, iy))
	for iy in freq_y:
		for xmy in freq_xmy:
			ix = iy + xmy
			mn = min(mn, tot_cost_to(ix, iy))
	for xpy in freq_xpy:
		for xmy in freq_xmy:
			ix = (xpy + xmy) / 2
			iy = xpy - ix
			mn = min(mn, tot_cost_to(ix, iy))
	pr(mn)


class point:

	def __init__(self, x, y):
		self.x = float(x)
		self.y = float(y)

	def vertical(self):
		a = 1
		b = 0
		c = -self.x
		return (a, b, c)

	def horizontal(self):
		a = 0
		b = 1
		c = -self.y
		return (a, b, c)

	def dig1(self):
		a = 1
		b = 1
		c = -(self.x + self.y)
		return (a, b, c)

	def dig2(self):
		a = 1
		b = -1
		c = -self.x + self.y
		return (a, b, c)

def intersect(p1, p2):
	a1 = p1[0]
	b1 = p1[1]
	a2 = p2[0]
	b2 = p2[1]
	if b1 == 0 and b2 == 0:
		return False
	if b1 == 0 or b2 == 0:
		return True
	if a1 / b1 == a2 / b2:
		return False
	else:
		return True

def intersectionpoint(l1, l2):
	a1 = l1[0]
	b1 = l1[1]
	c1 = l1[2]
	a2 = l2[0]
	b2 = l2[1]
	c2 = l2[2]
	a1b2_minus_a2b1 = a1 * b2 - a2 * b1
	x = (b1 * c2 - b2 * c1) / a1b2_minus_a2b1
	y = (c1 * a2 - c2 * a1) / a1b2_minus_a2b1
	if x == 0:
		x = 0
	if y == 0:
		y = 0
	return (x, y)

def update(dct, ip, p1, p2):
	if dct.get(ip, 0) == 0:
		dct[ip] = {(p1.x, p1.y), (p2.x, p2.y)}
	else:
		dct[ip].add((p1.x, p1.y))
		dct[ip].add((p2.x, p2.y))
t = int(input())
for q in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	dct = dict()
	for i in range(len(x)):
		x1 = x[i]
		y1 = y[i]
		p1 = point(x1, y1)
		if dct.get((p1.x, p1.y), 0) == 0:
			dct[p1.x, p1.y] = {(p1.x, p1.y)}
		for j in range(len(x)):
			if i == j:
				continue
			x2 = x[j]
			y2 = y[j]
			p2 = point(x2, y2)
			if intersect(p1.horizontal(), p2.vertical()):
				ip = intersectionpoint(p1.horizontal(), p2.vertical())
				update(dct, ip, p1, p2)
			if intersect(p1.horizontal(), p2.dig1()):
				ip = intersectionpoint(p1.horizontal(), p2.dig1())
				update(dct, ip, p1, p2)
			if intersect(p1.horizontal(), p2.dig2()):
				ip = intersectionpoint(p1.horizontal(), p2.dig2())
				update(dct, ip, p1, p2)
			if intersect(p1.vertical(), p2.horizontal()):
				ip = intersectionpoint(p1.vertical(), p2.horizontal())
				update(dct, ip, p1, p2)
			if intersect(p1.vertical(), p2.dig1()):
				ip = intersectionpoint(p1.vertical(), p2.dig1())
				update(dct, ip, p1, p2)
			if intersect(p1.vertical(), p2.dig2()):
				ip = intersectionpoint(p1.vertical(), p2.dig2())
				update(dct, ip, p1, p2)
			if intersect(p1.dig1(), p2.horizontal()):
				ip = intersectionpoint(p1.dig1(), p2.horizontal())
				update(dct, ip, p1, p2)
			if intersect(p1.dig1(), p2.vertical()):
				ip = intersectionpoint(p1.dig1(), p2.vertical())
				update(dct, ip, p1, p2)
			if intersect(p1.dig1(), p2.dig2()):
				ip = intersectionpoint(p1.dig1(), p2.dig2())
				update(dct, ip, p1, p2)
			if intersect(p1.dig2(), p2.horizontal()):
				ip = intersectionpoint(p1.dig2(), p2.horizontal())
				update(dct, ip, p1, p2)
			if intersect(p1.dig2(), p2.vertical()):
				ip = intersectionpoint(p1.dig2(), p2.vertical())
				update(dct, ip, p1, p2)
			if intersect(p1.dig2(), p2.dig1()):
				ip = intersectionpoint(p1.dig2(), p2.dig1())
				update(dct, ip, p1, p2)
	maximum = -1
	maxkey = -1
	for (k, v) in dct.items():
		if len(v) == maximum:
			if k in v:
				maxkey = k
		elif len(v) > maximum:
			maximum = len(v)
			maxkey = k
	if maxkey in dct[maxkey]:
		ans = len(dct[maxkey]) - 1 + (len(x) - len(dct[maxkey])) * 2
	else:
		ans = len(dct[maxkey]) + (len(x) - len(dct[maxkey])) * 2
	print(ans)


import collections
for _ in range(int(input())):
	n = int(input())
	X = list(map(int, input().split()))
	Y = list(map(int, input().split()))
	res = 1000000000
	for i in range(n):
		moves = 0
		for j in range(n):
			x = abs(X[i] - X[j])
			y = abs(Y[i] - Y[j])
			if x == 0 and y == 0:
				continue
			if x == 0 or y == 0:
				moves += 1
				continue
			if x == y:
				moves += 1
				continue
			moves += 2
		if moves < res:
			res = moves
	c1 = collections.Counter()
	c2 = collections.Counter()
	c3 = collections.Counter(Y)
	c4 = collections.Counter(X)
	P = {}
	for i in range(n):
		x = X[i]
		y = Y[i]
		c1.update([y - x])
		c2.update([y + x])
		P[str(x) + ',' + str(y)] = i
	for i in c1:
		for j in c2:
			px = (j - i) / 2
			py = (j + i) / 2
			if P.get(str(int(px)) + ',' + str(int(py))) != None:
				continue
			moves = 2 * n
			moves -= c1[py - px] + c2[py + px] + c3[py] + c4[px]
			if moves < res:
				res = moves
		for j in c3:
			px = j - i
			py = j
			if P.get(str(px) + ',' + str(py)) != None:
				continue
			moves = 2 * n
			moves -= c1[py - px] + c2[py + px] + c3[py] + c4[px]
			if moves < res:
				res = moves
		for j in c4:
			px = j
			py = j + i
			if P.get(str(px) + ',' + str(py)) != None:
				continue
			moves = 2 * n
			moves -= c1[py - px] + c2[py + px] + c3[py] + c4[px]
			if moves < res:
				res = moves
	for i in c2:
		for j in c3:
			px = i - j
			py = j
			if P.get(str(px) + ',' + str(py)) != None:
				continue
			moves = 2 * n
			moves -= c1[py - px] + c2[py + px] + c3[py] + c4[px]
			if moves < res:
				res = moves
		for j in c4:
			px = j
			py = i - j
			if P.get(str(px) + ',' + str(py)) != None:
				continue
			moves = 2 * n
			moves -= c1[py - px] + c2[py + px] + c3[py] + c4[px]
			if moves < res:
				res = moves
	for i in c3:
		for j in c4:
			px = j
			py = i
			if P.get(str(px) + ',' + str(py)) != None:
				continue
			moves = 2 * n
			moves -= c1[py - px] + c2[py + px] + c3[py] + c4[px]
			if moves < res:
				res = moves
	print(res)


from collections import defaultdict
t = int(input())
while t != 0:
	n = int(input())
	a = input().split()
	b = input().split()
	points = []
	for i in range(n):
		a[i] = float(a[i])
		b[i] = float(b[i])
		points.append([a[i], b[i]])
	mapa = defaultdict(int)
	cross = defaultdict(list)
	cols = defaultdict(int)
	rows = defaultdict(int)
	crosslines = defaultdict(int)
	for i in range(n):
		rows[a[i]] += 1
		cols[b[i]] += 1
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] == a[j] or b[i] == b[j] or a[j] - a[i] == b[j] - b[i] or (a[j] - a[i] == -(b[j] - b[i])):
				mapa[a[i], b[i]] += 1
				mapa[a[j], b[j]] += 1
			crossx1 = (a[i] + a[j] + b[i] - b[j]) / 2
			crossy1 = (a[i] - a[j] + b[i] + b[j]) / 2
			if [crossx1, crossy1] not in points:
				if (a[i], b[i]) not in cross[crossx1, crossy1]:
					cross[crossx1, crossy1].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx1, crossy1]:
					cross[crossx1, crossy1].append((a[j], b[j]))
			crossx2 = (a[i] + a[j] - b[i] + b[j]) / 2
			crossy2 = (a[j] - a[i] + b[i] + b[j]) / 2
			if [crossx2, crossy2] not in points:
				if (a[i], b[i]) not in cross[crossx2, crossy2]:
					cross[crossx2, crossy2].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx2, crossy2]:
					cross[crossx2, crossy2].append((a[j], b[j]))
			crossx3 = a[i]
			crossy3 = b[j]
			if [crossx3, crossy3] not in points:
				if (a[i], b[i]) not in cross[crossx3, crossy3]:
					cross[crossx3, crossy3].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx3, crossy3]:
					cross[crossx3, crossy3].append((a[j], b[j]))
			crossx4 = a[j]
			crossy4 = b[i]
			if [crossx4, crossy4] not in points:
				if (a[i], b[i]) not in cross[crossx4, crossy4]:
					cross[crossx4, crossy4].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx4, crossy4]:
					cross[crossx4, crossy4].append((a[j], b[j]))
			crossx5 = a[j]
			crossy5 = a[j] - a[i] + b[i]
			if [crossx5, crossy5] not in points:
				if (a[i], b[i]) not in cross[crossx5, crossy5]:
					cross[crossx5, crossy5].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx5, crossy5]:
					cross[crossx5, crossy5].append((a[j], b[j]))
			crossx6 = a[j]
			crossy6 = a[i] - a[j] + b[i]
			if [crossx6, crossy6] not in points:
				if (a[i], b[i]) not in cross[crossx6, crossy6]:
					cross[crossx6, crossy6].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx6, crossy6]:
					cross[crossx6, crossy6].append((a[j], b[j]))
			crossx7 = b[j] - b[i] + a[i]
			crossy7 = b[j]
			if [crossx7, crossy7] not in points:
				if (a[i], b[i]) not in cross[crossx7, crossy7]:
					cross[crossx7, crossy7].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx7, crossy7]:
					cross[crossx7, crossy7].append((a[j], b[j]))
			crossx8 = a[i] - b[j] + b[i]
			crossy8 = b[j]
			if [crossx8, crossy8] not in points:
				if (a[i], b[i]) not in cross[crossx8, crossy8]:
					cross[crossx8, crossy8].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx8, crossy8]:
					cross[crossx8, crossy8].append((a[j], b[j]))
			crossx9 = a[i]
			crossy9 = a[i] - a[j] + b[j]
			if [crossx9, crossy9] not in points:
				if (a[i], b[i]) not in cross[crossx9, crossy9]:
					cross[crossx9, crossy9].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx9, crossy9]:
					cross[crossx9, crossy9].append((a[j], b[j]))
			crossx10 = a[i]
			crossy10 = a[j] - a[i] + b[j]
			if [crossx10, crossy10] not in points:
				if (a[i], b[i]) not in cross[crossx10, crossy10]:
					cross[crossx10, crossy10].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx10, crossy10]:
					cross[crossx10, crossy10].append((a[j], b[j]))
			crossx11 = b[i] - b[j] + a[j]
			crossy11 = b[i]
			if [crossx11, crossy11] not in points:
				if (a[i], b[i]) not in cross[crossx11, crossy11]:
					cross[crossx11, crossy11].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx11, crossy11]:
					cross[crossx11, crossy11].append((a[j], b[j]))
			crossx12 = a[j] - b[i] + b[j]
			crossy12 = b[i]
			if [crossx12, crossy12] not in points:
				if (a[i], b[i]) not in cross[crossx12, crossy12]:
					cross[crossx12, crossy12].append((a[i], b[i]))
				if (a[j], b[j]) not in cross[crossx12, crossy12]:
					cross[crossx12, crossy12].append((a[j], b[j]))
	maxi1 = 0
	for key in mapa:
		if mapa[key] > maxi1:
			maxi1 = mapa[key]
	result1 = maxi1 + 2 * (n - 1 - maxi1)
	maxi2 = 0
	for key in cross:
		aux = len(cross[key]) + crosslines[key]
		if aux > maxi2:
			maxi2 = aux
	result2 = maxi2 + 2 * (n - maxi2)
	print(min(result1, result2))
	t = t - 1


from collections import defaultdict
testcases = int(input())
for t in range(testcases):
	N = int(input())
	X = list(map(int, input().split()))
	Y = list(map(int, input().split()))
	min_opr = int(1000)
	ONX = []
	ONY = []
	for p in range(N):
		count_opr = int(0)
		for q in range(N):
			if q > p:
				ONX.append((X[p] + X[q] - Y[p] + Y[q]) / 2)
				ONX.append(X[q])
				ONX.append(X[p] - Y[p] + Y[q])
				ONX.append((X[p] + X[q] + Y[p] - Y[q]) / 2)
				ONX.append(X[q])
				ONX.append(X[p] + Y[p] - Y[q])
				ONX.append(X[p])
				ONX.append(X[p])
				ONX.append(X[p])
				ONX.append(X[q] - Y[q] + Y[p])
				ONX.append(X[q] + Y[q] - Y[p])
				ONX.append(X[q])
				ONY.append((X[q] - X[p] + Y[p] + Y[q]) / 2)
				ONY.append(X[q] - X[p] + Y[p])
				ONY.append(Y[q])
				ONY.append((X[p] - X[q] + Y[p] + Y[q]) / 2)
				ONY.append(X[p] - X[q] + Y[p])
				ONY.append(Y[q])
				ONY.append(X[p] - X[q] + Y[q])
				ONY.append(X[q] - X[p] + Y[q])
				ONY.append(Y[q])
				ONY.append(Y[p])
				ONY.append(Y[p])
				ONY.append(Y[p])
			if p != q:
				if abs(X[p] - X[q]) == abs(Y[p] - Y[q]) or X[p] - X[q] == 0 or Y[p] - Y[q] == 0:
					count_opr += 1
				else:
					count_opr += 2
		if count_opr == N - 1:
			min_opr = count_opr
			break
		elif min_opr > count_opr:
			min_opr = count_opr
	frequencyXY = defaultdict(dict)
	for i in range(0, len(ONX), 12):
		for j in range(i, i + 12):
			if ONX[j] in frequencyXY.keys():
				if ONY[j] in frequencyXY[ONX[j]].keys():
					if frequencyXY[ONX[j]][ONY[j]][1] < i:
						frequencyXY[ONX[j]][ONY[j]][0] += 1
						frequencyXY[ONX[j]][ONY[j]][1] = i
				else:
					frequencyXY[ONX[j]][ONY[j]] = [1, i]
			else:
				frequencyXY[ONX[j]][ONY[j]] = [1, i]
	if min_opr > N:
		for k1 in frequencyXY.keys():
			for k2 in frequencyXY[k1].keys():
				count_opr = int(0)
				if frequencyXY[k1][k2][0] > 2 * N - min_opr - 1:
					for s in range(N):
						if abs(k1 - X[s]) == abs(k2 - Y[s]) or k1 - X[s] == 0 or k2 - Y[s] == 0:
							count_opr += 1
						else:
							count_opr += 2
					if count_opr == N:
						min_opr = count_opr
						break
					elif min_opr > count_opr:
						min_opr = count_opr
			if min_opr == N:
				break
	print(min_opr)


def getop(x, y, xl, yl, n):
	o = 0
	for j in range(n):
		xd = abs(x - xl[j])
		yd = abs(y - yl[j])
		if xd == 0 and yd == 0:
			continue
		if xd == 0 or yd == 0:
			o += 1
		elif xd == yd:
			o += 1
		else:
			o += 2
	return o
t = int(input())
for tc in range(t):
	n = int(input())
	xl = list(map(int, input().split()))
	yl = list(map(int, input().split()))
	mo = 2 * (n - 1)
	if n > 50:
		for i in range(n):
			x = xl[i]
			y = yl[i]
			mo = min(mo, getop(x, y, xl, yl, n))
			x = xl[i]
			y = xl[i]
			mo = min(mo, getop(x, y, xl, yl, n))
			x = yl[i]
			y = yl[i]
			mo = min(mo, getop(x, y, xl, yl, n))
			x = yl[i]
			y = xl[i]
			mo = min(mo, getop(x, y, xl, yl, n))
			for j in range(n):
				x = xl[i]
				y = yl[j]
				mo = min(mo, getop(x, y, xl, yl, n))
				x = xl[j]
				y = yl[i]
				mo = min(mo, getop(x, y, xl, yl, n))
		print(mo)
	else:
		for i in range(n):
			for j in range(n):
				x = (xl[i] + xl[j]) // 2
				y = (yl[i] + yl[j]) // 2
				mo = min(mo, getop(x, y, xl, yl, n))
				x = xl[i]
				y = yl[j]
				mo = min(mo, getop(x, y, xl, yl, n))
				c1 = xl[i] + yl[i]
				c2 = xl[j] - yl[j]
				x = (c1 + c2) / 2
				y = (c1 - c2) / 2
				mo = min(mo, getop(x, y, xl, yl, n))
				c3 = xl[i] + yl[i]
				x = xl[j]
				y = c3 - x
				mo = min(mo, getop(x, y, xl, yl, n))
				c4 = xl[i] + yl[i]
				y = yl[j]
				x = c4 - y
				mo = min(mo, getop(x, y, xl, yl, n))
				c5 = xl[i] - yl[i]
				x = xl[j]
				y = x - c5
				mo = min(mo, getop(x, y, xl, yl, n))
				c6 = xl[i] - yl[i]
				y = yl[j]
				x = c6 + y
				mo = min(mo, getop(x, y, xl, yl, n))
		print(mo)


def this_is_a_new_point(x, y, Ps):
	return (x, y) not in Ps

def check_point(x, y, Xs, Ys, Ls, Rs, n):
	found = Xs.get(x, 0) + Ys.get(y, 0) + Ls.get(x - y, 0) + Rs.get(x + y, 0)
	total = found + 2 * (n - found)
	return total
for _ in range(int(input())):
	n = int(input())
	X = list(map(int, input().split()))
	Y = list(map(int, input().split()))
	Xs = {}
	Ys = {}
	Ls = {}
	Rs = {}
	(L, R) = ([], [])
	Ps = set()
	for i in range(n):
		(x, y) = (X[i], Y[i])
		Ps.add((x, y))
		Xs[x] = Xs.get(x, 0) + 1
		Ys[y] = Ys.get(y, 0) + 1
		(l, r) = (x - y, x + y)
		L.append(l)
		R.append(r)
		Ls[l] = Ls.get(l, 0) + 1
		Rs[r] = Rs.get(r, 0) + 1
	best = None
	for i in range(n):
		found = Xs[X[i]] + Ys[Y[i]] + Ls[L[i]] + Rs[R[i]] - 4
		total = found + 2 * (n - 1 - found)
		if best is None or total < best:
			best = total
	for i in range(n - 1):
		x1 = X[i]
		y1 = Y[i]
		for j in range(i + 1, n):
			x2 = X[j]
			y2 = Y[j]
			sx = x1 + x2
			sy = y1 + y2
			dx = x2 - x1
			dy = y2 - y1
			new_possible_points = [(x1, y2), (x1, y2 - dx), (x1, y2 + dx), (x2, y1), (x2 - dy, y1), (x2 + dy, y1), (x2, y1 - dx), (x2, y1 + dx), (x1 + dy, y2), (x1 - dy, y2), ((sx - dy) / 2, (sy - dx) / 2), ((sx + dy) / 2, (sy + dx) / 2)]
			for (x, y) in new_possible_points:
				if this_is_a_new_point(x, y, Ps):
					best = min(best, check_point(x, y, Xs, Ys, Ls, Rs, n))
					Ps.add((x, y))
	print(best)


import numpy as np
try:

	class Solution:

		def Final(self, p1, p2, X, Y, N):
			ans = 0
			for i in range(N):
				x = p1 - X[i]
				y = p2 - Y[i]
				if x == 0 and y == 0:
					continue
				if x == 0 or y == 0:
					ans += 1
				elif abs(x) == abs(y):
					ans += 1
				else:
					ans += 2
			return ans
	for t in range(int(input())):
		N = int(input())
		X = list(map(int, input().split()))
		Y = list(map(int, input().split()))
		obj = Solution()
		ANS = float('inf')
		for i in range(N):
			for j in range(N):
				if N > 50:
					if i == j:
						break
				if i != j:
					p1 = X[i]
					p2 = Y[j]
					ANS = min(ANS, obj.Final(p1, p2, X, Y, N))
					temp1 = X[i] + Y[i]
					temp2 = X[j] - Y[j]
					temp3 = X[i] - Y[i]
					p1 = (temp1 + temp2) / 2
					p2 = (temp1 - temp2) / 2
					ANS = min(ANS, obj.Final(p1, p2, X, Y, N))
					p1 = temp1 - Y[j]
					p2 = Y[j]
					ANS = min(ANS, obj.Final(p1, p2, X, Y, N))
					p1 = temp3 + Y[j]
					p2 = Y[j]
					ANS = min(ANS, obj.Final(p1, p2, X, Y, N))
		print(ANS)
except EOFError as e:
	print(e)


from collections import Counter
N = int(input())
for _ in range(N):
	n = int(input())
	coords = set(zip(map(int, input().split()), map(int, input().split())))
	xs = Counter()
	ys = Counter()
	xy = Counter()
	yx = Counter()
	for (x, y) in coords:
		xs[x] += 1
		ys[y] += 1
		xy[x + y] += 1
		yx[y - x] += 1
	lines = []
	for i in xs:
		lines.append(('xs', i))
	for i in ys:
		lines.append(('ys', i))
	for i in xy:
		lines.append(('xy', i))
	for i in yx:
		lines.append(('yx', i))
	best_o = float('inf')
	for (x, y) in coords:
		singles = xs[x] + ys[y] + xy[x + y] + yx[y - x] - 4
		doubles = n - singles - 1
		ops = singles + doubles * 2
		best_o = min(best_o, ops)
	for i in range(len(lines)):
		for j in range(i + 1, len(lines)):
			(l_a, l_b) = sorted((lines[i], lines[j]))
			(lt_a, lv_a) = l_a
			(lt_b, lv_b) = l_b
			if lt_a == lt_b:
				continue
			x = None
			y = None
			x_y = None
			y_x = None
			if (lt_a, lt_b) == ('xs', 'xy'):
				x = lv_a
				x_y = lv_b
				y = x_y - x
				y_x = y - x
			elif (lt_a, lt_b) == ('xs', 'ys'):
				x = lv_a
				y = lv_b
				x_y = x + y
				y_x = y - x
			elif (lt_a, lt_b) == ('xs', 'yx'):
				x = lv_a
				y_x = lv_b
				y = x + y_x
				x_y = x + y
			elif (lt_a, lt_b) == ('xy', 'ys'):
				x_y = lv_a
				y = lv_b
				x = x_y - y
				y_x = y - x
			elif (lt_a, lt_b) == ('xy', 'yx'):
				x_y = lv_a
				y_x = lv_b
				if (x_y + y_x) % 2 == 0:
					y = int((x_y + y_x) / 2)
				if (y_x - x_y) % 2 == 0:
					x = int((x_y - y_x) / 2)
			elif (lt_a, lt_b) == ('ys', 'yx'):
				y = lv_a
				y_x = lv_b
				x = y - y_x
				x_y = x + y
			else:
				raise Exception(lt_a + ',' + lt_b)
			if (x, y) in coords:
				continue
			singles = xs[x] + ys[y] + xy[x_y] + yx[y_x]
			doubles = n - singles
			ops = singles + doubles * 2
			best_o = min(best_o, ops)
	print(best_o)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	xs = list(map(int, input().split()))
	ys = list(map(int, input().split()))
	(ver, hor, dg1, dg2) = (Counter() for _ in range(4))
	for (x, y) in zip(xs, ys):
		ver[x] += 1
		hor[y] += 1
		dg1[x + y] += 1
		dg2[x - y] += 1
	hashed = {(x, y) for (x, y) in zip(xs, ys)}
	ops = [[ver, hor, lambda u, v: (u, v)], [ver, dg1, lambda u, v: (u, v - u)], [ver, dg2, lambda u, v: (u, u - v)], [hor, dg1, lambda u, v: (v - u, u)], [hor, dg2, lambda u, v: (u + v, u)], [dg1, dg2, lambda u, v: ((u + v) // 2, (u - v) // 2) if (u + v) % 2 == 0 else 0]]
	(millor, fets) = (2 * (n - 1), {0})
	for (primer, segon, op) in ops:
		for u in primer:
			for v in segon:
				tp = op(u, v)
				if tp in fets:
					continue
				fets.add(tp)
				(x, y) = tp
				zero = tp in hashed
				if zero:
					uns = ver[x] + hor[y] + dg1[x + y] + dg2[x - y] - 4
				else:
					uns = 0
					if x in ver:
						uns += ver[x]
					if y in hor:
						uns += hor[y]
					if x + y in dg1:
						uns += dg1[x + y]
					if x - y in dg2:
						uns += dg2[x - y]
				dos = n - zero - uns
				value = uns + 2 * dos
				millor = min(millor, value)
	for u in dg1:
		for v in dg2:
			if (u + v) % 2 == 1:
				uns = dg1[u] + dg2[v]
				dos = n - uns
				value = uns + 2 * dos
				millor = min(millor, value)
	print(millor)


from sys import stdin, stdout

def check(h, k, x, y, n):
	s = 0
	for j in range(0, n):
		xx = h - x[j]
		yy = k - y[j]
		if xx == 0 and yy == 0:
			m = 0
		elif xx == 0 and yy != 0 or (xx != 0 and yy == 0):
			s = s + 1
		elif xx == yy or xx == -1 * yy:
			s = s + 1
		else:
			s = s + 2
	return s
t = int(stdin.readline())
for j in range(0, t):
	n = int(stdin.readline())
	x = list(map(int, stdin.readline().split()))
	y = list(map(int, stdin.readline().split()))
	ms = 1000000000
	for i in range(0, n):
		for l in range(i, n):
			h = (x[i] + x[l]) / 2
			k = (y[i] + y[l]) / 2
			ms = min(ms, check(h, k, x, y, n))
			h = x[i]
			k = y[l]
			ms = min(ms, check(h, k, x, y, n))
			c1 = x[i] + y[i]
			c2 = x[l] - y[l]
			h = (c1 + c2) / 2
			k = (c1 - c2) / 2
			ms = min(ms, check(h, k, x, y, n))
			c3 = x[i] + y[i]
			h = x[l]
			k = c3 - h
			ms = min(ms, check(h, k, x, y, n))
			c4 = x[i] + y[i]
			k = y[l]
			h = c4 - k
			ms = min(ms, check(h, k, x, y, n))
			c5 = x[i] - y[i]
			h = x[l]
			k = h - c5
			ms = min(ms, check(h, k, x, y, n))
			c6 = x[i] - y[i]
			k = y[l]
			h = c6 + k
			ms = min(ms, check(h, k, x, y, n))
	print(ms)


def point_intersection(i, j, a, c):
	if i == 0:
		if j == 1:
			y = (a + c) / 2
			x = y - c
		elif j == 2:
			x = c
			y = -x + a
		elif j == 3:
			y = c
			x = -y + a
	elif i == 1:
		if j == 2:
			x = c
			y = x + a
		elif j == 3:
			y = c
			x = y - a
	elif i == 2:
		if j == 3:
			x = a
			y = c
	return (x, y)
for _ in range(int(input())):
	N = int(input())
	X = list(map(int, input().split()))
	Y = list(map(int, input().split()))
	ans = 2 * N - 2
	point_lookup = {(X[i], Y[i]): i for i in range(N)}
	(GS, GD, GX, GY) = ({}, {}, {}, {})
	for i in range(N):
		(x, y) = (X[i], Y[i])
		if not x + y in GS:
			GS[x + y] = set()
		if not y - x in GD:
			GD[y - x] = set()
		if not x in GX:
			GX[x] = set()
		if not y in GY:
			GY[y] = set()
		GS[x + y].add(i)
		GD[y - x].add(i)
		GX[x].add(i)
		GY[y].add(i)
	G = [GS, GD, GX, GY]
	all_intersections = {}
	for i in range(3):
		for j in range(i + 1, 4):
			for (a, b) in G[i].items():
				for (c, d) in G[j].items():
					(px, py) = point_intersection(i, j, a, c)
					if not (px, py) in all_intersections:
						all_intersections[px, py] = set()
					all_intersections[px, py] = set.union(all_intersections[px, py], b, d)
	for (px, py) in all_intersections:
		points = all_intersections[px, py]
		op = 2 * (N - len(points)) + len(points)
		if (px, py) in point_lookup:
			op -= 1
		ans = min(op, ans)
	print(ans)


def update_cnt(m, key):
	val = 0
	if key in m.keys():
		val = m[key]
	m[key] = val + 1
	return m
t = int(input())
while t > 0:
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	ans = 1000000
	for i in range(n):
		st2 = 0
		st3 = 0
		hor = 0
		ver = 0
		mx = {}
		my = {}
		mpos = {}
		mneg = {}
		mpos[x[i], y[i]] = 1
		mneg[x[i], y[i]] = 1
		mx[x[i], y[i]] = 1
		my[x[i], y[i]] = 1
		for j in range(n):
			if i == j:
				continue
			if x[j] + y[i] - x[i] != y[j]:
				st2 += 1
				c1 = y[i] - x[i]
				c2 = y[j] + x[j]
				inx = (c2 - c1) / 2
				iny = (c1 + c2) / 2
				mpos = update_cnt(mpos, (inx, iny))
				mpos = update_cnt(mpos, (x[j], x[j] + c1))
				mpos = update_cnt(mpos, (y[j] - c1, y[j]))
			else:
				mpos = update_cnt(mpos, (x[j], y[j]))
			if y[i] + x[i] - x[j] != y[j]:
				st3 += 1
				c1_ = y[i] + x[i]
				c2_ = y[j] - x[j]
				inx_ = (c1_ - c2_) / 2
				iny_ = (c1_ + c2_) / 2
				mneg = update_cnt(mneg, (inx_, iny_))
				mneg = update_cnt(mneg, (x[j], c1_ - x[j]))
				mneg = update_cnt(mneg, (c1_ - y[j], y[j]))
			else:
				mneg = update_cnt(mneg, (x[j], y[j]))
			if x[i] != x[j]:
				ver += 1
				my = update_cnt(my, (x[i], y[j]))
			else:
				my = update_cnt(my, (x[j], y[j]))
			if y[i] != y[j]:
				hor += 1
				mx = update_cnt(mx, (x[j], y[i]))
			else:
				mx = update_cnt(mx, (x[j], y[j]))
		st2 += n - max(mpos.values())
		st3 += n - max(mneg.values())
		hor += n - max(mx.values())
		ver += n - max(my.values())
		ans = min([ans, st2, st3, hor, ver])
	print(ans)
	t = t - 1


from sys import stdin
inp = stdin.readline
t = int(inp())
for _ in range(t):
	n = int(inp())
	arrx = [int(x) for x in inp().split()]
	arry = [int(x) for x in inp().split()]
	(d1, d2, d3, d4) = (dict(), dict(), dict(), dict())
	for (x, y) in zip(arrx, arry):
		d1[x] = d1.get(x, 0) + 1
		d2[y] = d2.get(y, 0) + 1
		d3[y - x] = d3.get(y - x, 0) + 1
		d4[y + x] = d4.get(y + x, 0) + 1
	m = 0
	for (x, y) in zip(arrx, arry):
		m = max(m, d1[x] + d2[y] + d3[y - x] + d4[y + x] - 4)
	(l1, l2, l3, l4) = (max(d1.values()), max(d2.values()), max(d3.values()), max(d4.values()))
	m2 = max(l1 + l2, l1 + l3, l1 + l4, l2 + l3, l2 + l4, l3 + l4)
	m3 = 0
	for x in d1:
		for y in d2:
			if d3.get(y - x, 0) and (not (x, y) in zip(arrx, arry)):
				if d4.get(x + y, 0):
					m3 = max(m3, d1[x] + d2[y] + d3[y - x] + d4[x + y])
				else:
					m3 = max(m3, d1[x] + d2[y] + d3[y - x])
			elif d4.get(x + y, 0) and (not (x, y) in zip(arrx, arry)):
				m3 = max(m3, d1[x] + d2[y] + d4[x + y])
		for z in d3:
			y = z + x
			if d4.get(x + y, 0) and (not d2.get(y, 0)) and (not (x, y) in zip(arrx, arry)):
				m3 = max(m3, d1[x] + d3[z] + d4[x + y])
	for y in d2:
		for z in d3:
			x = y - z
			if d4.get(x + y, 0) and (not d1.get(x, 0)) and (not (x, y) in zip(arrx, arry)):
				m3 = max(m3, d2[y] + d3[z] + d4[x + y])
	print(min((n - 1) * 2 - m, n * 2 - m2, n * 2 - m3))


def inter(x1, y1, x2, y2, x3, y3, x4, y4):
	a1 = y2 - y1
	b1 = x1 - x2
	c1 = a1 * x1 + b1 * y1
	a2 = y4 - y3
	b2 = x3 - x4
	c2 = a2 * x3 + b2 * y3
	det = a1 * b2 - a2 * b1
	if det == 0:
		return ()
	x = (b2 * c1 - b1 * c2) / det
	y = (a1 * c2 - a2 * c1) / det
	return (x, y)

def onPoint(x, y):
	return [(x, 0), (0, y), (x + 1, y + 1), (x - 1, y + 1)]

def maxOfDict(ans):
	v = 0
	k = []
	for i in ans:
		if ans[i] > v:
			k = [i]
			v = ans[i]
		elif ans[i] == v:
			k.append(i)
	return k

def allPoints(x, y, n):
	ans = {}
	for key in range(n - 1):
		(cx, cy) = (x[key], y[key])
		diff = cx - cy
		add = cx + cy
		cxp = onPoint(cx, cy)
		for i in range(key + 1, n):
			if y[i] == cy or x[i] == cx or diff == x[i] - y[i] or (add == x[i] + y[i]):
				continue
			else:
				other = onPoint(x[i], y[i])
				for p in cxp:
					for q in other:
						it = inter(cx, cy, p[0], p[1], x[i], y[i], q[0], q[1])
						if len(it) == 2:
							ans[it] = ans.get(it, 0) + 1
	return maxOfDict(ans)
t = int(input())
while t:
	t -= 1
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	ans = 10000
	points = allPoints(x, y, n)
	for j in range(len(points)):
		if j == n:
			break
		it = points[j]
		(cx, cy) = (it[0], it[1])
		diff = cx - cy
		add = cx + cy
		move = 0
		for i in range(n):
			if x[i] == cx and y[i] == cy:
				continue
			elif y[i] == cy or x[i] == cx or diff == x[i] - y[i] or (add == x[i] + y[i]):
				move += 1
			else:
				move += 2
		ans = min(ans, move)
	for key in range(n):
		(cx, cy) = (x[key], y[key])
		move = 0
		diff = cx - cy
		add = cx + cy
		for i in range(n):
			if x[i] == cx and y[i] == cy:
				continue
			elif y[i] == cy or x[i] == cx or diff == x[i] - y[i] or (add == x[i] + y[i]):
				move += 1
			else:
				move += 2
		ans = min(ans, move)
	print(ans)


t = int(input())

def intersection(L1, L2):
	D = L1[0] * L2[1] - L1[1] * L2[0]
	Dx = L1[2] * L2[1] - L1[1] * L2[2]
	Dy = L1[0] * L2[2] - L1[2] * L2[0]
	if D != 0:
		x = Dx / D
		y = Dy / D
		return (x, y)
	else:
		return None
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	points = {(x[i], y[i]) for i in range(n)}
	lines = {}
	for i in range(n):
		lines[1, 0, x[i]] = 0
		lines[0, 1, y[i]] = 0
		lines[1, -1, x[i] - y[i]] = 0
		lines[1, 1, x[i] + y[i]] = 0
	for i in range(n):
		for l in lines:
			if l[0] * x[i] + l[1] * y[i] == l[2]:
				lines[l] += 1
	ans = 2 * n
	lines_list = list(lines.keys())
	intersection_points = {}
	for i in range(len(lines_list)):
		for j in range(i):
			l1 = lines_list[i]
			l2 = lines_list[j]
			intersect = intersection(l1, l2)
			if intersect is not None:
				(a, b) = (int(intersect[0]), int(intersect[1]))
				if l1[0] * a + l1[1] * b == l1[2] and l2[0] * a + l2[1] * b == l2[2]:
					intersect = (a, b)
				if intersect not in intersection_points:
					intersection_points[intersect] = {l1, l2}
				else:
					intersection_points[intersect].add(l1)
					intersection_points[intersect].add(l2)
			else:
				curr = max(lines[l1], lines[l2])
				curr += (n - curr) * 2 - 1
				ans = min(curr, ans)
	for (key, value) in intersection_points.items():
		curr = 0
		intersect_in_p = False
		if key in points:
			intersect_in_p = True
		for l in value:
			curr += lines[l] - intersect_in_p
		curr += (n - curr - intersect_in_p) * 2
		ans = min(curr, ans)
	print(ans)


from collections import defaultdict
for tcase in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	linex = defaultdict(list)
	liney = defaultdict(list)
	lines = defaultdict(list)
	lined = defaultdict(list)
	for i in range(n):
		(xi, yi) = (x[i], y[i])
		linex[xi].append(i)
		liney[yi].append(i)
		lines[xi + yi].append(i)
		lined[xi - yi].append(i)
	points = set(((x[i], y[i]) for i in range(n)))
	isec = set()
	for i in range(n):
		(xi, yi) = (x[i], y[i])
		(si, di) = (xi + yi, xi - yi)
		for j in range(n):
			(xj, yj) = (x[j], y[j])
			(sj, dj) = (xj + yj, xj - yj)
			isec.add((xi, yj))
			if i != j:
				isec.add((xi, sj - xi))
				isec.add((xi, xi - dj))
				isec.add((xj, yi))
				isec.add((sj - yi, yi))
				isec.add((dj + yi, yi))
				isec.add((xj, si - xj))
				isec.add((si - yj, yj))
				isec.add(((si + dj) / 2, (si - dj) / 2))
				isec.add((xj, xj - di))
				isec.add((di + yj, yj))
				isec.add(((sj + di) / 2, (sj - di) / 2))
	result = []
	for (xi, yi) in isec:
		r = 2 * n - len(linex[xi]) - len(liney[yi]) - len(lines[xi + yi]) - len(lined[xi - yi])
		if (xi, yi) in points:
			r += 2
		result.append(r)
	print(min(result))