Captain Marmot wants to prepare a huge and important battle against his enemy, Captain Snake. For this battle he has n regiments, each consisting of 4 moles.

Initially, each mole i (1 ≤ i ≤ 4n) is placed at some position (x_{i}, y_{i}) in the Cartesian plane. Captain Marmot wants to move some moles to make the regiments compact, if it's possible.

Each mole i has a home placed at the position (a_{i}, b_{i}). Moving this mole one time means rotating his position point (x_{i}, y_{i}) 90 degrees counter-clockwise around it's home point (a_{i}, b_{i}).

A regiment is compact only if the position points of the 4 moles form a square with non-zero area.

Help Captain Marmot to find out for each regiment the minimal number of moves required to make that regiment compact, if it's possible.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 100), the number of regiments.

The next 4n lines contain 4 integers x_{i}, y_{i}, a_{i}, b_{i} ( - 10^4 ≤ x_{i}, y_{i}, a_{i}, b_{i} ≤ 10^4).


-----Output-----

Print n lines to the standard output. If the regiment i can be made compact, the i-th line should contain one integer, the minimal number of required moves. Otherwise, on the i-th line print "-1" (without quotes).


-----Examples-----
Input
4
1 1 0 0
-1 1 0 0
-1 1 0 0
1 -1 0 0
1 1 0 0
-2 1 0 0
-1 1 0 0
1 -1 0 0
1 1 0 0
-1 1 0 0
-1 1 0 0
-1 1 0 0
2 2 0 1
-1 0 0 -2
3 0 0 -2
-1 1 -2 0

Output
1
-1
3
3



-----Note-----

In the first regiment we can move once the second or the third mole.

We can't make the second regiment compact.

In the third regiment, from the last 3 moles we can move once one and twice another one.

In the fourth regiment, we can move twice the first mole and once the third mole.

Difficulty: HARD
Tags: Geometry

Complete search
Skill types: Complete search

Starter code:

Solutions:
n = int(input())
(a, c) = ([0] * 4, [0] * 4)

def rotate(i, j):
	(x, y, p, q) = a[i]
	for k in range(1, j + 1):
		(x, y) = (p - (y - q), q + (x - p))
	c[i] = (x, y)

def dist(i, j):
	((x, y), (p, q)) = (c[i], c[j])
	return (x - p) ** 2 + (y - q) ** 2

def check(move):
	for i in range(4):
		rotate(i, move[i])
	p = [1, 2, 3]
	p.sort(key=lambda x: dist(0, x))
	d = [dist(0, x) for x in p]
	return d[0] == d[1] == d[2] // 2 and d[2] > 0 and (dist(p[0], p[1]) == d[2])
for i in range(n):
	a[0] = list(map(int, input().split()))
	a[1] = list(map(int, input().split()))
	a[2] = list(map(int, input().split()))
	a[3] = list(map(int, input().split()))
	res = 17
	for k in range(4):
		for l in range(4):
			for p in range(4):
				for q in range(4):
					if check([k, l, p, q]):
						res = min(res, k + l + p + q)
	print(res if res != 17 else -1)


import copy
import sys

def solve():
	n = int(input())
	for reg in range(n):
		temp = help()
		print(-1 if temp == 1000 else temp)

def help():
	res = 1000
	read = [list(map(int, input().split())) for _ in range(4)]
	for _1 in range(4):
		for _2 in range(4):
			for _3 in range(4):
				for _4 in range(4):
					l = copy.deepcopy(read)
					for i in range(_1):
						rot(l[0])
					for i in range(_2):
						rot(l[1])
					for i in range(_3):
						rot(l[2])
					for i in range(_4):
						rot(l[3])
					if square(l):
						res = min(res, _1 + _2 + _3 + _4)
	return res

def rot(l):
	x = l[0]
	y = l[1]
	homex = l[2]
	homey = l[3]
	yabove = y - homey
	xright = x - homex
	newx = homex - yabove
	newy = homey + xright
	l[0] = newx
	l[1] = newy
	return l

def square(l):
	distances = list()
	for i in range(4):
		for j in range(i + 1, 4):
			distances.append(dist(l[i], l[j]))
	distances.sort()
	if distances[0] < 1e-06:
		return False
	different = 0
	for i in range(len(distances) - 1):
		if abs(distances[i] - distances[i + 1]) > 1e-06:
			different += 1
	return different == 1

def dist(a, b):
	return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1])
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


def f(x, y, a, b, n):
	return (a + (x - a) * cos[n] - (y - b) * sin[n], b + (x - a) * sin[n] + (y - b) * cos[n])

def check(p):
	d = {}
	for i in range(len(p) - 1):
		for j in range(i + 1, len(p)):
			dist = (p[i][0] - p[j][0]) ** 2 + (p[i][1] - p[j][1]) ** 2
			d[dist] = d.get(dist, 0) + 1
	if len(d) != 2:
		return 0
	(a, b) = sorted(d)
	return 2 * a == b and d[a] == 4 and (d[b] == 2)
(cos, sin, variants) = ([1, 0, -1, 0], [0, 1, 0, -1], [[x, y, z, a] for x in range(4) for y in range(4) for z in range(4) for a in range(4)])
for t in range(int(input())):
	(moles, ans) = ([list(map(int, input().split())) for x in range(4)], 13)
	for a in variants:
		if check([f(moles[i][0], moles[i][1], moles[i][2], moles[i][3], a[i]) for i in range(4)]):
			ans = min(ans, sum(a))
	print(ans if ans != 13 else -1)


def distSq(p, q):
	return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])

def isSquare(p1, p2, p3, p4):
	d2 = distSq(p1, p2)
	d3 = distSq(p1, p3)
	d4 = distSq(p1, p4)
	if d2 == 0 or d3 == 0 or d4 == 0:
		return False
	if d2 == d3 and 2 * d2 == d4 and (2 * distSq(p2, p4) == distSq(p2, p3)):
		return True
	if d3 == d4 and 2 * d3 == d2 and (2 * distSq(p3, p2) == distSq(p3, p4)):
		return True
	if d2 == d4 and 2 * d2 == d3 and (2 * distSq(p2, p3) == distSq(p2, p4)):
		return True
	return False
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	arr = []
	for i in range(4):
		temp = [int(x) for x in input().split()]
		arr.append(temp)

	def helper(curr, temp, m):
		if curr == 4:
			if isSquare(temp[0], temp[1], temp[2], temp[3]):
				return m
			return sys.maxsize
		ans = sys.maxsize
		(sx, sy) = (arr[curr][0], arr[curr][1])
		for i in range(4):
			temp.append([sx, sy])
			ans = min(ans, helper(curr + 1, temp, m + i))
			temp.pop()
			p = sx
			sx = -(sy - arr[curr][3]) + arr[curr][2]
			sy = p - arr[curr][2] + arr[curr][3]
		return ans
	ans = helper(0, [], 0)
	if ans == sys.maxsize:
		print(-1)
	else:
		print(ans)


3
from itertools import product, combinations

def process(case):
	regiment = map(rotate, homes, positions, case)
	return sum(case) if is_square(regiment) else float('inf')

def is_square(regiment):
	dists = list(map(lambda arg: dist_sq(*arg), combinations(regiment, 2)))
	dists.sort()
	return 0 < dists[0] == dists[3] < dists[4] == dists[5]

def dist_sq(p1, p2):
	return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

def rotate(home, position, step):
	((x, y), (a, b)) = (position, home)
	if step == 0:
		return (x, y)
	if step == 1:
		return (a - (y - b), b + (x - a))
	if step == 2:
		return (a - (x - a), b - (y - b))
	if step == 3:
		return (a + (y - b), b - (x - a))
n = int(input())
for r in range(n):
	positions = []
	homes = []
	for i in range(4):
		(x, y, a, b) = map(int, input().split())
		positions.append((x, y))
		homes.append((a, b))
	all_cases = product(range(4), repeat=4)
	result = min(map(process, all_cases))
	print(result if result != float('inf') else -1)


from sys import stdin
from itertools import product
lines = list([_f for _f in stdin.read().split('\n') if _f])

def parseline(line):
	return list(map(int, line.split()))
lines = list(map(parseline, lines))
n = lines[0][0]
assert len(lines) >= 4 * n + 1

class Unit:

	def __init__(self, x, y, a, b):
		self.pos = (x, y)
		self.home = (a, b)

def to_unit(l):
	return Unit(l[0], l[1], l[2], l[3])

def squads():
	for i in range(n):
		yield list(map(to_unit, lines[4 * i + 1:4 * i + 5]))

def is_90_degree(a, b, c, d):
	return 0 == sum(((bi - ai) * (di - ci) for (ai, bi, ci, di) in zip(a, b, c, d)))

def dist_sqr(a, b):
	return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2

def is_square(points):
	(a, b, c, d) = points
	if a == b == c == d:
		return False
	if not is_90_degree(a, b, c, d):
		(b, d) = (d, b)
		if not is_90_degree(a, b, c, d):
			(a, d) = (d, a)
			if not is_90_degree(a, b, c, d):
				return False
	if not (c[0] + d[0] == b[0] + a[0] and c[1] + d[1] == b[1] + a[1]):
		return False
	if not dist_sqr(a, b) == dist_sqr(c, d):
		return False
	return True

def rotate(point, pole, angle):
	result = point
	for i in range(angle):
		result = (-result[1] + pole[1] + pole[0], result[0] - pole[0] + pole[1])
	return result

def rotate_squad(squad, rotation):
	return [rotate(unit.pos, unit.home, angle) for (unit, angle) in zip(squad, rotation)]
rotations = list(product([0, 1, 2, 3], repeat=4))
INF = 10000000
for squad in squads():
	min_rotations = INF
	for rotation in rotations:
		if is_square(rotate_squad(squad, rotation)):
			min_rotations = min(min_rotations, sum(rotation))
	if min_rotations == INF:
		min_rotations = -1
	print(min_rotations)


def r(t):
	(t[0], t[1]) = (t[2] + t[3] - t[1], t[3] + t[0] - t[2])
f = [(0, 0), (1, 3), (2, 15), (3, 63)]
h = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
g = lambda u, v: (u[0] - v[0]) ** 2 + (u[1] - v[1]) ** 2
for i in range(int(input())):
	p = [list(map(int, input().split())) for j in range(4)]
	s = 13
	for q in range(256):
		t = sum((q >> k & 3 for k in (0, 2, 4, 6)))
		d = sorted((g(p[u], p[v]) for (u, v) in h))
		if 0 != d[4] == d[5] == 2 * d[0] == 2 * d[3]:
			s = min(s, t)
		for (i, k) in f:
			if q & k == k:
				r(p[i])
	print(s if s < 13 else -1)


import sys
input = sys.stdin.readline

def distSq(p1, p2):
	return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1])

def isSquare(p1, p2, p3, p4):
	d2 = distSq(p1, p2)
	d3 = distSq(p1, p3)
	d4 = distSq(p1, p4)
	if d2 == d3 and 2 * d2 == d4 and (2 * distSq(p2, p4) == distSq(p2, p3)):
		return True
	if d3 == d4 and 2 * d3 == d2 and (2 * distSq(p3, p2) == distSq(p3, p4)):
		return True
	if d2 == d4 and 2 * d2 == d3 and (2 * distSq(p2, p3) == distSq(p2, p4)):
		return True
	return False
for _ in range(int(input())):
	l = []
	for i in range(4):
		(x, y, a, b) = map(int, input().split())
		for j in range(4):
			l.append([x, y, j])
			(x, y) = (a + b - y, x + b - a)
	mini = 10 ** 9
	for i in range(4):
		for j in range(4, 8):
			for k in range(8, 12):
				for z in range(12, 16):
					if l[i] == l[j] or l[j] == l[k] or l[i] == l[k] or (l[i] == l[z]) or (l[j] == l[z]) or (l[k] == l[z]):
						continue
					if isSquare(l[i], l[j], l[k], l[z]):
						curr = l[i][2] + l[j][2] + l[k][2] + l[z][2]
						if curr < mini:
							mini = curr
	print(mini if mini < 10 ** 9 else -1)


def rotate(x, y, a, b):
	x = x - a
	y = y - b
	new_y = x
	new_x = -y
	new_x = new_x + a
	new_y = new_y + b
	return [new_x, new_y]

def marmot_distance(x1, y1, x2, y2):
	answer = pow(pow(x2 - x1, 2) + pow(y2 - y1, 2), 0.5)
	return answer

def beethovens_command(formation):
	for first in range(4):
		for second in range(4):
			for third in range(4):
				for fourth in range(4):
					distance_1 = 0
					distance_2 = 0
					uncompact = False
					for d in range(4):
						for e in range(d + 1, 4):
							distance_0 = marmot_distance(formation[e][0], formation[e][1], formation[d][0], formation[d][1])
							if distance_0 == 0:
								uncompact = True
							if distance_1 == 0:
								distance_1 = distance_0
							elif distance_2 == 0 and distance_0 != distance_1:
								distance_2 = distance_0
							if distance_0 != distance_1 and distance_0 != distance_2:
								uncompact = True
					if distance_1 > distance_2:
						big_marmot = distance_1
						distance_1 = distance_2
						distance_2 = big_marmot
					if pow(2 * pow(distance_1, 2), 0.5) == distance_2 and (not uncompact):
						print(first + second + third + fourth)
						return
					else:
						pass
					(formation[3][0], formation[3][1]) = rotate(formation[3][0], formation[3][1], formation[3][2], formation[3][3])
				(formation[2][0], formation[2][1]) = rotate(formation[2][0], formation[2][1], formation[2][2], formation[2][3])
			(formation[1][0], formation[1][1]) = rotate(formation[1][0], formation[1][1], formation[1][2], formation[1][3])
		(formation[0][0], formation[0][1]) = rotate(formation[0][0], formation[0][1], formation[0][2], formation[0][3])
	print('-1')
	return
regiments = int(input())
for i in range(regiments):
	formation = []
	for t in range(4):
		temp = [int(num) for num in input().split()]
		formation.append(temp)
	beethovens_command(formation)


def siblings(initial, root):
	th = (initial[0] - root[0], initial[1] - root[1])
	return [(root[0] + th[0], root[1] + th[1]), (root[0] - th[1], root[1] + th[0]), (root[0] - th[0], root[1] - th[1]), (root[0] + th[1], root[1] - th[0])]

def dist(x, y):
	return (x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2

def isSquare(p1, p2, p3, p4):
	d2 = dist(p1, p2)
	d3 = dist(p1, p3)
	d4 = dist(p1, p4)
	u = {p1, p2, p3, p4}
	if len(u) != 4:
		return 0
	if d2 == d3 and 2 * d2 == d4:
		d = dist(p2, p4)
		return d == dist(p3, p4) and d == d2
	if d3 == d4 and 2 * d3 == d2:
		d = dist(p2, p3)
		return d == dist(p2, p4) and d == d3
	if d2 == d4 and 2 * d2 == d3:
		d = dist(p2, p3)
		return d == dist(p3, p4) and d == d2
	return False

def distOri(x, y, root):
	th1 = (y[0] - root[0], y[1] - root[1])
	th2 = (x[0] - root[0], x[1] - root[1])
	if th1[0] == th2[0] and th1[1] == th2[1]:
		return 0
	if th2[0] == -th1[1] and th2[1] == th1[0]:
		return 1
	if th2[0] == -th1[0] and th2[1] == -th1[1]:
		return 2
	if th2[0] == th1[1] and th2[1] == -th1[0]:
		return 3
n = int(input())
for i in range(n):
	initial = []
	root = []
	_min = 1000
	for j in range(4):
		(x, y, a, b) = [int(k) for k in input().split()]
		initial.append((x, y))
		root.append((a, b))
	for x1 in siblings(initial[0], root[0]):
		for x2 in siblings(initial[1], root[1]):
			for x3 in siblings(initial[2], root[2]):
				for x4 in siblings(initial[3], root[3]):
					if isSquare(x1, x2, x3, x4):
						_min = min(_min, distOri(x1, initial[0], root[0]) + distOri(x2, initial[1], root[1]) + distOri(x3, initial[2], root[2]) + distOri(x4, initial[3], root[3]))
	if _min == 1000:
		print(-1)
	else:
		print(_min)


class Point:

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

def distSq(p, q):
	return (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y)

def isSquare(p1, p2, p3, p4):
	d2 = distSq(p1, p2)
	d3 = distSq(p1, p3)
	d4 = distSq(p1, p4)
	if d2 == 0 or d3 == 0 or d4 == 0:
		return False
	if d2 == d3 and 2 * d2 == d4 and (2 * distSq(p2, p4) == distSq(p2, p3)):
		return True
	if d3 == d4 and 2 * d3 == d2 and (2 * distSq(p3, p2) == distSq(p3, p4)):
		return True
	if d2 == d4 and 2 * d2 == d3 and (2 * distSq(p2, p3) == distSq(p2, p4)):
		return True
	return False
n = int(input())
for _ in range(n):
	r = []
	for i in range(4):
		(x, y, a, b) = list(map(int, input().split()))
		r.append([[x, y], [a + b - y, x + b - a], [2 * a - x, 2 * b - y], [a - b + y, a + b - x]])
	ans = 64
	f = 0
	(r1, r2, r3, r4) = r
	for i in range(4):
		for j in range(4):
			for k in range(4):
				for l in range(4):
					p1 = Point(r1[i][0], r1[i][1])
					p2 = Point(r2[j][0], r2[j][1])
					p3 = Point(r3[k][0], r3[k][1])
					p4 = Point(r4[l][0], r4[l][1])
					if isSquare(p1, p2, p3, p4):
						f = 1
						ans = min(ans, i + j + k + l)
	if f:
		print(ans)
	else:
		print(-1)


def r(t):
	(t[0], t[1]) = (t[2] + t[3] - t[1], t[3] + t[0] - t[2])
f = range(4)
g = lambda u, v: (u[0] - v[0]) ** 2 + (u[1] - v[1]) ** 2
h = [(i, j) for i in f for j in f if i < j]
for i in range(int(input())):
	p = [list(map(int, input().split())) for j in f]
	s = 13
	for a in f:
		for b in f:
			for c in f:
				for d in f:
					t = sorted((g(p[u], p[v]) for (u, v) in h))
					if 0 != t[4] == t[5] == 2 * t[0] == 2 * t[3]:
						s = min(s, a + b + c + d)
					r(p[3])
				r(p[2])
			r(p[1])
		r(p[0])
	print(s if s < 13 else -1)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		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 = os.read(self._fd, max(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 = os.read(self._fd, max(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:
			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')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 10 ** 9 + 7
EPS = 1e-06

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def RotateAntiClockBy90(P, H):
	(x, y) = P
	(a, b) = H
	x -= a
	y -= b
	X = -y + a
	Y = x + b
	return (X, Y)

def Dist(p1, p2):
	return (p2[1] - p1[1]) ** 2 + (p2[0] - p1[0]) ** 2

def isSquare(P):
	(p1, p2, p3, p4) = P
	d2 = Dist(p1, p2)
	d3 = Dist(p1, p3)
	d4 = Dist(p1, p4)
	if d2 == 0 or d3 == 0 or d4 == 0:
		return False
	if d2 == d3 and 2 * d2 == d4 and (2 * Dist(p2, p4) == Dist(p2, p3)):
		return True
	if d3 == d4 and 2 * d3 == d2 and (2 * Dist(p3, p2) == Dist(p3, p4)):
		return True
	if d2 == d4 and 2 * d2 == d3 and (2 * Dist(p2, p3) == Dist(p2, p4)):
		return True
	return False
for _ in range(Int()):
	home = []
	point = []
	for i in range(4):
		V = value()
		point.append((V[0], V[1]))
		home.append((V[2], V[3]))
	ans = [inf]
	heapify(ans)
	for i in range(4):
		point[0] = RotateAntiClockBy90(point[0], home[0])
		cost1 = (i + 1) % 4
		for j in range(4):
			cost2 = (j + 1) % 4
			point[1] = RotateAntiClockBy90(point[1], home[1])
			for k in range(4):
				cost3 = (k + 1) % 4
				point[2] = RotateAntiClockBy90(point[2], home[2])
				for l in range(4):
					cost4 = (l + 1) % 4
					point[3] = RotateAntiClockBy90(point[3], home[3])
					if isSquare(point):
						heappush(ans, cost1 + cost2 + cost3 + cost4)
	ans = heappop(ans)
	if ans == inf:
		ans = -1
	print(ans)


def rotate(p):
	return [-p[1] + p[2] + p[3], -p[2] + p[3] + p[0], p[2], p[3]]

def isS(P):
	X = [P[0][0] * 4, P[1][0] * 4, P[2][0] * 4, P[3][0] * 4]
	Y = [P[0][1] * 4, P[1][1] * 4, P[2][1] * 4, P[3][1] * 4]
	p = sum(X) // 4
	q = sum(Y) // 4
	r = [(X[i] - p) ** 2 + (Y[i] - q) ** 2 for i in range(4)]
	if len(set(r)) != 1:
		return False
	for i in range(4):
		for j in range(i + 1, 4):
			if X[i] == X[j] and Y[i] == Y[j]:
				return False
	for i in range(4):
		for j in range(i + 1, 4):
			(k, l) = list(set([0, 1, 2, 3]) - set([i, j]))
			t1 = (X[i] - X[k]) ** 2 + (Y[i] - Y[k]) ** 2
			t2 = (X[i] - X[l]) ** 2 + (Y[i] - Y[l]) ** 2
			t3 = (X[j] - X[k]) ** 2 + (Y[j] - Y[k]) ** 2
			t4 = (X[j] - X[l]) ** 2 + (Y[j] - Y[l]) ** 2
			if t1 == t2 == t3 == t4:
				return True
	return False
N = int(input())
for i in range(N):
	res = []
	P = []
	for j in range(4):
		p = list(map(int, input().split(' ')))
		P.append(p)
	for k1 in range(4):
		for k2 in range(4):
			for k3 in range(4):
				for k4 in range(4):
					if isS(P):
						res.append(k1 + k2 + k3 + k4)
					P[3] = rotate(P[3])
				P[2] = rotate(P[2])
			P[1] = rotate(P[1])
		P[0] = rotate(P[0])
	res = min(res) if res else -1
	print(res)


n = int(input())

def isSquare(a, b, c, d):
	if 2 * ((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2) == 2 * ((c[0] - a[0]) ** 2 + (c[1] - a[1]) ** 2) == (d[0] - a[0]) ** 2 + (d[1] - a[1]) ** 2 == (b[0] - c[0]) ** 2 + (b[1] - c[1]) ** 2 == 2 * ((d[0] - c[0]) ** 2 + (d[1] - c[1]) ** 2) == 2 * ((d[0] - b[0]) ** 2 + (d[1] - b[1]) ** 2) and a != d:
		return True
	return False
for reg in range(n):
	moles = []
	for i in range(4):
		moles.append([int(x) for x in input().split()])
	pos = []
	for (x, y, a, b) in moles:
		x -= a
		y -= b
		p = [(x, y)]
		for bruh in range(3):
			(x, y) = (-y, x)
			p.append((x, y))
		pos.append([(c[0] + a, c[1] + b) for c in p])
	low = float('inf')
	for a in range(4):
		for b in range(4):
			for c in range(4):
				for d in range(4):
					points = [pos[0][a], pos[1][b], pos[2][c], pos[3][d]]
					points.sort()
					if isSquare(points[0], points[1], points[2], points[3]):
						low = min(low, a + b + c + d)
	if low == float('inf'):
		print(-1)
	else:
		print(low)


import sys
inf = float('inf')

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

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

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

def function(x, y):
	return [[x, y], [-y, x], [-x, -y], [y, -x]]

def give_me(x, y, a, b):
	(x, y) = (x - a, y - b)
	lst = function(x, y)
	for i in range(4):
		lst[i][0] += a
		lst[i][1] += b
	return lst

def distsq(p, q):
	return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])

def is_square(p1, p2, p3, p4):
	if p1 == p2 == p3 == p4:
		return False
	d2 = distsq(p1, p2)
	d3 = distsq(p1, p3)
	d4 = distsq(p1, p4)
	if d2 == d3 and 2 * d2 == d4 and (2 * distsq(p2, p4) == distsq(p2, p3)):
		return True
	if d3 == d4 and 2 * d3 == d2 and (2 * distsq(p3, p2) == distsq(p3, p4)):
		return True
	if d2 == d4 and 2 * d2 == d3 and (2 * distsq(p2, p3) == distsq(p2, p4)):
		return True
	return False
n = int(input())
for m in range(n):
	(x1, y1, a1, b1) = get_ints()
	(x2, y2, a2, b2) = get_ints()
	(x3, y3, a3, b3) = get_ints()
	(x4, y4, a4, b4) = get_ints()
	lst1 = give_me(x1, y1, a1, b1)
	lst2 = give_me(x2, y2, a2, b2)
	lst3 = give_me(x3, y3, a3, b3)
	lst4 = give_me(x4, y4, a4, b4)
	flag = 0
	mini = inf
	for (i, w) in enumerate(lst1):
		for (j, x) in enumerate(lst2):
			for (k, y) in enumerate(lst3):
				for (l, z) in enumerate(lst4):
					if is_square(w, x, y, z):
						flag = 1
						curr = i + j + k + l
						if curr < mini:
							mini = curr
	if flag == 0:
		print(-1)
	else:
		print(mini)


import math
import copy

def getRot(mPos):
	x = mPos[0]
	y = mPos[1]
	aX = mPos[2]
	aY = mPos[3]
	oldX = x - aX
	oldY = y - aY
	newX = oldY
	newY = oldX
	newX *= -1
	newX += aX
	newY += aY
	return [newX, newY]

def getRotArr(mPosArr):
	rotmPosArr = []
	for mPos in mPosArr:
		rotmPos = []
		x = mPos[0]
		y = mPos[1]
		aX = mPos[2]
		aY = mPos[3]
		oldX = x - aX
		oldY = y - aY
		for _ in range(4):
			rotmPos.append(oldX + aX)
			rotmPos.append(oldY + aY)
			newX = oldY
			newY = oldX
			newX *= -1
			oldX = newX
			oldY = newY
		rotmPosArr.append(rotmPos)
	return rotmPosArr

def isCompact(rotmPos):
	INF = 9876543
	nCompact = INF
	for i in range(4):
		for j in range(4):
			for k in range(4):
				for l in range(4):
					posArr = []
					posArr.append([rotmPos[0][2 * i], rotmPos[0][2 * i + 1]])
					posArr.append([rotmPos[1][2 * j], rotmPos[1][2 * j + 1]])
					posArr.append([rotmPos[2][2 * k], rotmPos[2][2 * k + 1]])
					posArr.append([rotmPos[3][2 * l], rotmPos[3][2 * l + 1]])
					maxX = max((posArr[m][0] for m in range(4)))
					minX = min((posArr[m][0] for m in range(4)))
					maxY = max((posArr[m][1] for m in range(4)))
					minY = min((posArr[m][1] for m in range(4)))
					if abs(maxX - minX) == abs(maxY - minY) and isSquare(posArr):
						nCompact = min(nCompact, i + j + k + l)
	if nCompact == INF:
		nCompact = -1
	print(nCompact)

def isSquare(posArr):
	for i in range(4):
		for j in range(i + 1, 4):
			if posArr[i] == posArr[j]:
				return False
	avgX = sum((posArr[i][0] for i in range(4))) / 4
	avgY = sum((posArr[i][1] for i in range(4))) / 4
	tempPosArr = copy.deepcopy(posArr)
	rotPosA = getRot([tempPosArr[0][0], tempPosArr[0][1], avgX, avgY])
	tempPosArr.pop(0)
	for _ in range(3):
		for tempPos in tempPosArr:
			if rotPosA == tempPos:
				tempPosArr.remove(tempPos)
				break
		rotPosA = getRot([tempPos[0], tempPos[1], avgX, avgY])
	if len(tempPosArr) > 0:
		return False
	else:
		return True

def getDist(posA, posB):
	return math.sqrt((posA[0] - posB[0]) ** 2 + (posA[1] - posB[1]) ** 2)
mPosArr = []
nRegiment = int(input())
for i in range(nRegiment * 4):
	mPos = list(map(int, input().split(' ')))
	mPosArr.append(mPos)
rotmPosArr = getRotArr(mPosArr)
for i in range(nRegiment):
	isCompact(rotmPosArr[i * 4:i * 4 + 4])