You are given two points $P$ and $Q$ and an opaque sphere in a three-dimensional space. The point $P$ is not moving, while $Q$ is moving in a straight line with constant velocity. You are also given a direction vector $d$ with the following meaning: the position of $Q$ at time $t$ is $Q(t) = Q(0) + d \cdot t$, where $Q(0)$ is the initial position of $Q$.
It is guaranteed that $Q$ is not visible from $P$ initially (at time $t=0$). It is also guaranteed that $P$ and $Q$ do not touch the sphere at any time.
Find the smallest positive time $t_v$ when $Q$ is visible from $P$, i.e. when the line segment connecting points $P$ and $Q$ does not intersect the sphere.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains 13 space-separated integers.
- The first three integers $P_x, P_y, P_z$ denote the coordinates of $P$.
- The next three integers $Q_x, Q_y, Q_z$ denote the initial coordinates of $Q$.
- The next three integers $d_x, d_y, d_z$ denote the components of the direction vector $d$.
- The last four integers $c_x, c_y, c_z, r$ denote the coordinates of the centre of the sphere and its radius.

-----Output-----
For each test case, print a single line containing one real number — the time $t_v$. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$. It is guaranteed that $t_v$ exists and does not exceed $10^9$.

-----Constraints-----
- $1 \le T \le 10^5$
- the absolute values of coordinates of all points do not exceed $2\cdot10^9$
- $1 \le r \le 10^9$

-----Subtasks-----
Subtask #1 (25 points): $P_z = Q_z = d_z = c_z = 0$
Subtask #2 (75 points): original constraints

-----Example Input-----
1
3 0 0 -10 -10 0 0 10 0 0 -3 0 3

-----Example Output-----
1.0000000000

Difficulty: MEDIUM_HARD
Tags: Geometry

Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
t = input().strip()
t = int(t)
for _ in range(t):
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(float, input().strip().split())
	a = qx - px
	b = qy - py
	c = qz - pz
	k = px - cx
	l = py - cy
	m = pz - cz
	S1 = r ** 2 * (dx ** 2 + dy ** 2 + dz ** 2)
	S2 = (dx * l - dy * k) ** 2 + (dy * m - dz * l) ** 2 + (dz * k - dx * m) ** 2
	A = S1 - S2
	S1 = 2 * r ** 2 * (a * dx + b * dy + c * dz)
	S2 = 2 * ((a * l - b * k) * (dx * l - dy * k) + (b * m - c * l) * (dy * m - dz * l) + (c * k - a * m) * (dz * k - dx * m))
	B = S1 - S2
	S1 = r ** 2 * (a ** 2 + b ** 2 + c ** 2)
	S2 = (a * l - b * k) ** 2 + (b * m - c * l) ** 2 + (c * k - a * m) ** 2
	C = S1 - S2
	if A == 0:
		t = -1 * C / B
		print(round(t, 10))
	else:
		import math
		t1 = (-1 * B + math.sqrt(B ** 2 - 4 * A * C)) / (2 * A)
		t2 = (-1 * B - math.sqrt(B ** 2 - 4 * A * C)) / (2 * A)
		if t1 < 0 and t2 < 0:
			print(round(0, 10))
		elif t1 < 0:
			print(round(t2, 10))
		elif t2 < 0:
			print(round(t1, 10))
		elif t1 >= t2:
			print(round(t1, 10))
		else:
			print(round(t2, 10))


import functools
import math
t = int(input())
p = [0, 0, 0]
q = [0, 0, 0]
d = [0, 0, 0]
c = [0, 0, 0]
for i in range(t):
	(p[0], p[1], p[2], q[0], q[1], q[2], d[0], d[1], d[2], c[0], c[1], c[2], r) = map(int, input().split())
	qp = [q[i] - p[i] for i in [0, 1, 2]]
	cp = [c[i] - p[i] for i in [0, 1, 2]]
	cpd = functools.reduce(lambda x, y: x + y, [cp[i] * d[i] for i in [1, 2, 0]])
	qpd = functools.reduce(lambda x, y: x + y, [qp[i] * d[i] for i in [1, 2, 0]])
	cpqp = functools.reduce(lambda x, y: x + y, [cp[i] * qp[i] for i in [1, 2, 0]])
	cp2 = functools.reduce(lambda x, y: x + y, [cp[i] * cp[i] for i in [1, 2, 0]])
	qp2 = functools.reduce(lambda x, y: x + y, [qp[i] * qp[i] for i in [1, 2, 0]])
	d2 = functools.reduce(lambda x, y: x + y, [d[i] * d[i] for i in [0, 1, 2]])
	l = cp2 - r * r
	A = cpd * cpd - l * d2
	B = cpd * cpqp - l * qpd
	C = cpqp * cpqp - l * qp2
	if A == 0:
		ans = -1 * C / (2 * B)
	else:
		ans = (math.sqrt(B * B - A * C) - B) / A
		if ans < 0:
			ans = (-1 * math.sqrt(B * B - A * C) - B) / A
	print(ans)


import math

def f():
	user = input().split(' ')
	x1 = int(user[0])
	y1 = int(user[1])
	z1 = int(user[2])
	Qx = int(user[3])
	Qy = int(user[4])
	Qz = int(user[5])
	Dx = int(user[6])
	Dy = int(user[7])
	Dz = int(user[8])
	x3 = int(user[9])
	y3 = int(user[10])
	z3 = int(user[11])
	r = int(user[12])
	time = 0
	x2 = Qx + Dx * time
	y2 = Qy + Dy * time
	z2 = Qz + Dz * time
	a = (x2 - x1) ** 2 + (y2 - y1) ** 2 + (z2 - z1) ** 2
	b = 2 * ((x2 - x1) * (x1 - x3) + (y2 - y1) * (y1 - y3) + (z2 - z1) * (z1 - z3))
	c = x3 ** 2 + y3 ** 2 + z3 ** 2 + x1 ** 2 + y1 ** 2 + z1 ** 2 - 2 * (x3 * x1 + y3 * y1 + z3 * z1) - r ** 2
	bpart1 = (Qx - x1) * (x1 - x3) + (Qy - y1) * (y1 - y3) + (Qz - z1) * (z1 - z3)
	bpart2 = Dx * (x1 - x3) + Dy * (y1 - y3) + Dz * (z1 - z3)
	apart1 = (Qx - x1) ** 2 + (Qy - y1) ** 2 + (Qz - z1) ** 2
	apart2 = Dx ** 2 + Dy ** 2 + Dz ** 2
	apart3 = (Qx - x1) * Dx + (Qy - y1) * Dy + (Qz - z1) * Dz
	tpart1 = bpart2 ** 2 - c * apart2
	tpart2 = 2 * (bpart1 * bpart2 - c * apart3)
	tpart3 = bpart1 ** 2 - c * apart1
	if tpart1 == 0:
		sol1 = -tpart3 / tpart2
		sol2 = -tpart3 / tpart2
	else:
		d = tpart2 ** 2 - 4 * tpart1 * tpart3
		sol1 = (-tpart2 - math.sqrt(d)) / (2 * tpart1)
		sol2 = (-tpart2 + math.sqrt(d)) / (2 * tpart1)
	max = 10 ** 10
	if sol1 > 0 and sol1 <= max:
		max = sol1
	if sol2 > 0 and sol2 <= max:
		max = sol2
	return max
t = int(input())
for i in range(t):
	print(f())


def dot(a, b):
	r = a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
	return r
for _ in range(int(input())):
	(x1, y1, z1, x2, y2, z2, d1, d2, d3, c1, c2, c3, r) = map(float, input().split())
	a = x2 - x1
	b = y2 - y1
	c = z2 - z1
	k = x1 - c1
	l = y1 - c2
	m = z1 - c3
	term1 = r ** 2 * d1 ** 2 + r ** 2 * d2 ** 2 + r ** 2 * d3 ** 2
	term2 = (d1 * l - d2 * k) ** 2 + (d2 * m - d3 * l) ** 2 + (d3 * k - d1 * m) ** 2
	A = term1 - term2
	term11 = 2 * r ** 2 * (a * d1 + b * d2 + c * d3)
	term22 = 2 * ((a * l - b * k) * (d1 * l - d2 * k) + (b * m - c * l) * (d2 * m - d3 * l) + (c * k - a * m) * (d3 * k - d1 * m))
	B = term11 - term22
	ter1 = r ** 2 * (a ** 2 + b ** 2 + c ** 2)
	ter2 = (a * l - b * k) ** 2 + (b * m - c * l) ** 2 + (c * k - a * m) ** 2
	C = ter1 - ter2
	if A == 0:
		t = -1 * C / B
		print(t)
		continue
	else:
		t1 = (-1 * B + (B ** 2 - 4 * A * C) ** 0.5) / (2 * A)
		t2 = (-1 * B - (B ** 2 - 4 * A * C) ** 0.5) / (2 * A)
		t = 0
		if t1 < 0:
			t = t2
		elif t2 < 0:
			t = t1
		elif t1 >= 0 and t2 >= 0:
			t = min(t1, t2)
		print(t)


from math import sqrt as sqrt

def sqr(x):
	return x * x

class coordinates:
	x = 0.0
	y = 0.0
	z = 0.0

	def mins(self, a):
		b = coordinates()
		b.x = self.x - a.x
		b.y = self.y - a.y
		b.z = self.z - a.z
		return b
test = int(input())
while test:
	test -= 1
	p = coordinates()
	q = coordinates()
	d = coordinates()
	c = coordinates()
	arr = input().split()
	p.x = float(arr[0])
	p.y = float(arr[1])
	p.z = float(arr[2])
	q.x = float(arr[3])
	q.y = float(arr[4])
	q.z = float(arr[5])
	d.x = float(arr[6])
	d.y = float(arr[7])
	d.z = float(arr[8])
	c.x = float(arr[9])
	c.y = float(arr[10])
	c.z = float(arr[11])
	r = float(arr[12])
	dist_rp = sqrt(sqr(c.x - p.x) + sqr(c.y - p.y) + sqr(c.z - p.z))
	sinth = r / dist_rp
	costh = sqrt(1 - sqr(sinth))
	c_p = coordinates()
	qmp = coordinates()
	c_p = c.mins(p)
	qmp = q.mins(p)
	udvf = c_p.x * qmp.x + c_p.y * qmp.y + c_p.z * qmp.z
	udvs = c_p.x * d.x + c_p.y * d.y + c_p.z * d.z
	mag_u = sqrt(sqr(c_p.x) + sqr(c_p.y) + sqr(c_p.z))
	denm = sqr(mag_u) * sqr(costh)
	mag_qmp = sqrt(sqr(qmp.x) + sqr(qmp.y) + sqr(qmp.z))
	mag_d = sqrt(sqr(d.x) + sqr(d.y) + sqr(d.z))
	qmpdd = qmp.x * d.x + qmp.y * d.y + qmp.z * d.z
	a = sqr(mag_d) - sqr(udvs) / denm
	b = 2 * (qmpdd - udvf * udvs / denm)
	c = sqr(mag_qmp) - sqr(udvf) / denm
	if a < 10 ** (-10):
		t = -1.0 * c / b
	else:
		determ = sqrt(sqr(b) - 4 * a * c)
		sh = (determ - b) / (2 * a)
		ev = (-determ - b) / (2 * a)
		if ev < 0 or sh < 0:
			t = max(ev, sh)
		else:
			t = min(ev, sh)
	print(t)


for _ in range(int(input())):
	(x1, y1, z1, x2, y2, z2, d1, d2, d3, c1, c2, c3, r) = map(float, input().split())
	cc = z2 - z1
	kk = x1 - c1
	aa = x2 - x1
	bb = y2 - y1
	l = y1 - c2
	mm = z1 - c3
	ta1 = (d1 * l - d2 * kk) ** 2 + (d2 * mm - d3 * l) ** 2 + (d3 * kk - d1 * mm) ** 2
	rr = r ** 2
	ta2 = rr * d1 * d1 + rr * d2 * d2 + rr * d3 * d3
	tb1 = 2 * (aa * l - bb * kk) * (d1 * l - d2 * kk) + 2 * (bb * mm - cc * l) * (d2 * mm - d3 * l)
	tb1 += 2 * (cc * kk - aa * mm) * (d3 * kk - d1 * mm)
	tb2 = 2 * aa * rr * d1 + 2 * bb * rr * d2 + 2 * cc * rr * d3
	tc1 = (aa * l - bb * kk) * (aa * l - bb * kk) + (bb * mm - cc * l) * (bb * mm - cc * l) + (cc * kk - aa * mm) * (cc * kk - aa * mm)
	tc2 = aa * aa * rr + bb * bb * rr + cc * cc * rr
	fta = ta2 - ta1
	ftb = tb2 - tb1
	ftc = tc2 - tc1
	if fta != 0:
		ans1 = (-1 * ftb + (ftb ** 2 - 4 * fta * ftc) ** 0.5) / (2 * fta)
		ans2 = (-1 * ftb - (ftb ** 2 - 4 * fta * ftc) ** 0.5) / (2 * fta)
		ans3 = 0
		if ans1 < 0:
			ans3 = ans2
		elif ans2 < 0:
			ans3 = ans1
		elif ans1 > 0 and ans2 > 0:
			ans3 = min(ans1, ans2)
	else:
		ans3 = -ftc / ftb
	print(ans3)


from operator import mul, sub
dot = lambda x, y: sum(map(mul, x, y))
t = int(input())
for _ in range(t):
	l = map(int, input().split())
	R = lambda : (next(l), next(l), next(l))
	(p, q, d, c, r) = (R(), R(), R(), R(), next(l))
	q = tuple(map(sub, q, p))
	c = tuple(map(sub, c, p))
	(cc, qc, dc) = (dot(x, c) for x in (c, q, d))
	q = tuple((x - qc / cc * y for (x, y) in zip(q, c)))
	d = tuple((x - dc / cc * y for (x, y) in zip(d, c)))
	r *= r
	r /= (cc - r) * cc
	a = dot(d, d) - dc * dc * r
	b = dot(q, d) - qc * dc * r
	c = dot(q, q) - qc * qc * r
	if a:
		print(((b * b - a * c) ** 0.5 - b) / a)
	else:
		print(-c / (2 * b))


import math
t = int(input())
while t > 0:
	q = map(int, input().split(' '))
	p = list(q)
	x1 = p[0]
	y1 = p[1]
	z1 = p[2]
	x2 = p[3]
	y2 = p[4]
	z2 = p[5]
	dx = p[6]
	dy = p[7]
	dz = p[8]
	x3 = p[9]
	y3 = p[10]
	z3 = p[11]
	r = p[12]
	a = (x1 - x3) * (x2 - x1) + (y1 - y3) * (y2 - y1) + (z1 - z3) * (z2 - z1)
	b = (x1 - x3) * dx + (y1 - y3) * dy + (z1 - z3) * dz
	d = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1)
	e = 2 * ((x2 - x1) * dx + (y2 - y1) * dy + (z2 - z1) * dz)
	f = dx * dx + dy * dy + dz * dz
	A = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3) + (z1 - z3) * (z1 - z3)
	x = r * r * f - A * f + b * b
	y = r * r * e - A * e + 2 * a * b
	z = r * r * d - A * d + a * a
	D = pow(y * y - 4 * x * z, 1 / 2)
	if x == 0:
		D1 = -z / y
	else:
		D1 = (-y - D) / (2 * x)
	print(D1)
	t = t - 1


T = int(input())
while T:
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(int, input().split())
	x = qx - px
	y = qy - py
	z = qz - pz
	a = px - cx
	b = py - cy
	c = pz - cz
	e = a * a + b * b + c * c
	x1 = r * r + a * a - e
	y1 = r * r + b * b - e
	z1 = r * r + c * c - e
	A = x1 * dx * dx + y1 * dy * dy + z1 * dz * dz + 2 * (a * b * dx * dy + c * b * dz * dy + a * c * dx * dz)
	B = 2 * (x1 * x * dx + y1 * y * dy + z1 * z * dz + a * b * x * dy + a * b * y * dx + a * c * x * dz + a * c * z * dx + c * b * z * dy + c * b * y * dz)
	C = x1 * x * x + y1 * y * y + z1 * z * z + 2 * a * b * x * y + 2 * a * c * x * z + 2 * c * b * z * y
	if A != 0:
		discr = B * B - 4 * A * C
		discr = discr ** 0.5
		root1 = (-1 * B + discr) / (2 * A)
		root2 = (-1 * B - discr) / (2 * A)
		if root1 >= 0 and root2 >= 0:
			if root1 > root2:
				print(root1)
			else:
				print(root2)
		elif root1 >= 0:
			print(root1)
		else:
			print(root2)
	else:
		time = -1 * C / B
		print(time)
	T -= 1


from math import *
T = int(input())
for _ in range(T):
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(int, input().split())
	M = px - cx
	N = py - cy
	P = pz - cz
	PT2 = M ** 2 + N ** 2 + P ** 2 - r ** 2
	a = (-2 * dx * M - 2 * dy * N - 2 * dz * P) ** 2 - 4 * PT2 * (dx ** 2 + dy ** 2 + dz ** 2)
	b = -1 * ((4 * dx * M + 4 * dy * N + 4 * dz * P) * (px ** 2 + py ** 2 + pz ** 2 - cx ** 2 - cy ** 2 - cz ** 2 - 2 * (qx * M + qy * N + qz * P) + r ** 2 - PT2) + 4 * PT2 * (2 * qx * dx + 2 * qy * dy + 2 * qz * dz - 2 * cx * dx - 2 * cy * dy - 2 * cz * dz))
	c = (px ** 2 + py ** 2 + pz ** 2 - cx ** 2 - cy ** 2 - cz ** 2 - 2 * (qx * M + qy * N + qz * P) + r ** 2 - PT2) ** 2 - 4 * PT2 * (cx ** 2 + cy ** 2 + cz ** 2 + qx ** 2 + qy ** 2 + qz ** 2 - 2 * cx * qx - 2 * cy * qy - 2 * cz * qz - r ** 2)
	ANS = 0
	if a == 0:
		ANS = -c / b
	else:
		D = (b ** 2 - 4 * a * c) ** (1 / 2)
		first = (-1 * b - D) / (2 * a)
		zz = 0
		second = (-1 * b + D) / (2 * a)
		minn = min(second, first)
		if minn < 0:
			if minn == first:
				zz = second
			else:
				zz = first
		ANS = zz
	print('%.10f' % ANS)


import math
T = int(input())
for t in range(T):
	(Px, Py, Pz, Qx, Qy, Qz, dx, dy, dz, xo, yo, zo, r) = list(map(float, input().strip().split(' ')))
	(kpox, kpoy, kpoz) = (Px - xo, Py - yo, Pz - zo)
	(kpqx, kpqy, kpqz) = (Px - Qx, Py - Qy, Pz - Qz)
	c1 = kpox ** 2 + kpoy ** 2 + kpoz ** 2 - r ** 2
	k1 = kpox * kpqx + kpoy * kpqy + kpoz * kpqz
	k2 = dx * kpox + dy * kpoy + dz * kpoz
	a1 = k2 ** 2
	b1 = -2 * k1 * k2
	a = a1 - (dx ** 2 + dy ** 2 + dz ** 2) * c1
	b = c1 * 2 * (dx * kpqx + dy * kpqy + dz * kpqz) + b1
	c = c1 * (-kpqx ** 2 - kpqy ** 2 - kpqz ** 2) + k1 ** 2
	if a != 0:
		ans = (-b - (b ** 2 - 4 * a * c) ** (1 / 2)) / (2 * a)
	else:
		ans = -c / b
	print(ans)


import math
tests = int(input())

def roots(x1, y1, z1, x2, y2, z2, dx, dy, dz, x3, y3, z3, r):
	mx = x2 - x1
	my = y2 - y1
	mz = z2 - z1
	nx = x1 - x3
	ny = y1 - y3
	nz = z1 - z3
	K = x3 ** 2 + y3 ** 2 + z3 ** 2 + x1 ** 2 + y1 ** 2 + z1 ** 2 - 2 * (x3 * x1 + y3 * y1 + z3 * z1) - r ** 2
	A = dx * dx * (nx * nx - K) + dy * dy * (ny * ny - K) + dz * dz * (nz * nz - K) + 2 * nx * ny * dx * dy + 2 * ny * nz * dy * dz + 2 * nz * nx * dz * dx
	B = (nx * nx - K) * (2 * mx * dx) + (ny * ny - K) * (2 * my * dy) + (nz * nz - K) * (2 * mz * dz) + 2 * (nx * ny * my * dx + nx * ny * mx * dy + ny * nz * mz * dy + ny * nz * my * dz + nz * nx * mz * dx + nz * nx * mx * dz)
	C = nx * nx * mx * mx + ny * ny * my * my + nz * nz * mz * mz + 2 * nx * ny * mx * my + 2 * ny * nz * my * mz + 2 * nz * nx * mz * mx - K * mx * mx - K * my * my - K * mz * mz
	d = B * B - 4 * A * C
	if A != 0:
		sol1 = (-B - math.sqrt(d)) / (2 * A)
		sol2 = (-B + math.sqrt(d)) / (2 * A)
		if sol1 > 0 and sol2 > 0:
			return min(sol1, sol2)
		elif sol1 >= 0:
			return sol1
		elif sol2 >= 0:
			return sol2
	elif A == 0:
		return -C / B
for tester in range(tests):
	arr = input().split()
	(p1, p2, p3, q1, q2, q3, d1, d2, d3, c1, c2, c3, r) = (int(x) for x in arr)
	ans = roots(p1, p2, p3, q1, q2, q3, d1, d2, d3, c1, c2, c3, r)
	print('%.6f' % ans)


import math
te = int(input())
while te > 0:
	te = te - 1
	(x1, y1, z1, x2, y2, z2, d1, d2, d3, x0, y0, z0, r) = input().split()
	x1 = int(x1)
	y1 = int(y1)
	z1 = int(z1)
	x2 = int(x2)
	y2 = int(y2)
	z2 = int(z2)
	d1 = int(d1)
	d2 = int(d2)
	d3 = int(d3)
	x0 = int(x0)
	y0 = int(y0)
	z0 = int(z0)
	r = int(r)
	A = (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0) + (z1 - z0) * (z1 - z0)
	C = A - r * r
	a = x1 - x0
	b = y1 - y0
	c = z1 - z0
	AA = (C - a * a) * (d1 * d1) + (C - b * b) * (d2 * d2) + (C - c * c) * (d3 * d3) - 2 * a * b * d1 * d2 - 2 * b * c * d2 * d3 - 2 * a * c * d1 * d3
	BB = (C - a * a) * d1 * (x2 - x1) + (C - b * b) * d2 * (y2 - y1) + (C - c * c) * d3 * (z2 - z1) - a * b * (d1 * (y2 - y1) + d2 * (x2 - x1)) - b * c * (d2 * (z2 - z1) + d3 * (y2 - y1)) - a * c * (d1 * (z2 - z1) + d3 * (x2 - x1))
	CC = (C - a * a) * (x2 - x1) * (x2 - x1) + (C - b * b) * (y2 - y1) * (y2 - y1) + (C - c * c) * (z2 - z1) * (z2 - z1) - 2 * a * b * (x2 - x1) * (y2 - y1) - 2 * b * c * (y2 - y1) * (z2 - z1) - 2 * a * c * (x2 - x1) * (z2 - z1)
	BB *= 2
	if AA == 0:
		t1 = -CC / BB
		print(t1)
	else:
		cal = math.sqrt(BB * BB - 4 * AA * CC)
		t1 = (-BB + cal) / (2 * AA)
		t2 = (-BB - cal) / (2 * AA)
		if t2 < 0:
			print(t1)
		else:
			print(t2)


import math
T = int(input())
for i in range(T):
	L = list(map(int, input().split()))
	(Px, Py, Pz, Qx, Qy, Qz, dx, dy, dz, cx, cy, cz, r) = (L[0], L[1], L[2], L[3], L[4], L[5], L[6], L[7], L[8], L[9], L[10], L[11], L[12])
	qpx = Qx - Px
	qpy = Qy - Py
	qpz = Qz - Pz
	pcx = Px - cx
	pcy = Py - cy
	pcz = Pz - cz
	m = (Px - cx) * (Px - cx) + (Py - cy) * (Py - cy) + (Pz - cz) * (Pz - cz)
	mx = m - r * r - pcx * pcx
	my = m - r * r - pcy * pcy
	mz = m - r * r - pcz * pcz
	a = mx * dx * dx + my * dy * dy + mz * dz * dz - 2 * pcx * pcy * dx * dy - 2 * pcy * pcz * dy * dz - 2 * pcx * pcz * dx * dz
	b = 2 * mx * qpx * dx + 2 * my * qpy * dy + 2 * mz * qpz * dz - 2 * pcx * pcy * (qpx * dy + qpy * dx) - 2 * pcy * pcz * (qpy * dz + qpz * dy) - 2 * pcx * pcz * (qpz * dx + qpx * dz)
	c = mx * qpx * qpx + my * qpy * qpy + mz * qpz * qpz
	c = c - 2 * pcx * pcy * qpx * qpy
	c = c - 2 * pcy * pcz * qpy * qpz
	c = c - 2 * pcz * pcx * qpz * qpx
	if a != 0:
		det = b * b - 4 * a * c
		det = math.sqrt(det)
		det1 = (det - b) / (2 * a)
		det2 = -1 * (b + det) / (2 * a)
		if det1 > det2:
			det = det1
		else:
			det = det2
		print(det)
	else:
		det = -1 * (c / b)
		print(det)


import math
t = int(input())
for l in range(t):
	(px, py, pz, qx, qy, qz, x, y, z, cx, cy, cz, r) = map(int, input().split())
	a = cx - px
	b = cy - py
	c = cz - pz
	g = cx - qx
	h = cy - qy
	i = cz - qz
	m = px - qx
	n = py - qy
	v = pz - qz
	at1 = a * a * y * y + a * a * z * z - 2 * a * b * x * y - 2 * a * c * x * z + b * b * x * x + b * b * z * z - 2 * b * c * y * z + c * c * x * x + c * c * y * y - r * r * x * x - r * r * y * y - r * r * z * z
	bt1 = -2 * a * a * h * y - 2 * a * a * i * z + 2 * a * b * g * y + 2 * a * b * h * x + 2 * a * c * g * z + 2 * a * c * i * x - 2 * b * b * g * x - 2 * b * b * i * z + 2 * b * c * h * z + 2 * b * c * i * y - 2 * c * c * g * x - 2 * c * c * h * y + 2 * m * r * r * x + 2 * n * r * r * y + 2 * r * r * v * z
	ct1 = a * a * h * h + a * a * i * i - 2 * a * b * g * h - 2 * a * c * g * i + b * b * g * g + b * b * i * i - 2 * b * c * h * i + c * c * g * g + c * c * h * h - m * m * r * r - n * n * r * r - r * r * v * v
	at1 = -1 * at1
	bt1 = -1 * bt1
	ct1 = -1 * ct1
	if at1 == 0:
		ans = abs(-1 * (ct1 / bt1))
		print(ans)
	else:
		ans1 = (-bt1 + math.sqrt(bt1 * bt1 - 4 * at1 * ct1)) / (2 * at1)
		ans2 = (-bt1 - math.sqrt(bt1 * bt1 - 4 * at1 * ct1)) / (2 * at1)
		if ans1 > 0:
			print(ans1)
		if ans2 > 0:
			print(ans2)


from operator import mul, sub
from itertools import islice
dot = lambda x, y: sum(map(mul, x, y))
t = int(input())
for _ in range(t):
	l = map(int, input().split())
	(p, q, d, c) = islice(iter(lambda : tuple(islice(l, 3)), None), 4)
	r = next(l)
	q = tuple(map(sub, q, p))
	c = tuple(map(sub, c, p))
	cc = dot(c, c)
	qc = dot(q, c)
	dc = dot(d, c)
	(qcc, dcc) = (qc / cc, dc / cc)
	q = tuple((x - qcc * y for (x, y) in zip(q, c)))
	d = tuple((x - dcc * y for (x, y) in zip(d, c)))
	r *= r
	r /= (cc - r) * cc
	a = dot(d, d) - dc * dc * r
	b = dot(q, d) - qc * dc * r
	c = dot(q, q) - qc * qc * r
	if a:
		print(((b * b - a * c) ** 0.5 - b) / a)
	else:
		print(-c / (2 * b))


from math import sqrt
t = int(input())
for test in range(t):
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(int, input().split())
	c2 = qx - px
	c3 = qy - py
	c4 = qz - pz
	c5 = px - cx
	c6 = py - cy
	c7 = pz - cz
	c1 = c5 * c5 + c6 * c6 + c7 * c7 - r * r
	a = c5 * c5 * dx * dx + c6 * c6 * dy * dy + c7 * c7 * dz * dz + 2 * c5 * c6 * dx * dy + 2 * c6 * c7 * dy * dz + 2 * c5 * c7 * dx * dz - c1 * (dx * dx + dy * dy + dz * dz)
	b = 2 * c2 * dx * c5 * c5 + 2 * c3 * dy * c6 * c6 + 2 * c4 * dz * c7 * c7 + 2 * (c5 * c6 * (c2 * dy + c3 * dx) + c6 * c7 * (c3 * dz + c4 * dy) + c5 * c7 * (c4 * dx + c2 * dz)) - c1 * (2 * c2 * dx + 2 * c3 * dy + 2 * c4 * dz)
	c = c5 * c5 * c2 * c2 + c6 * c6 * c3 * c3 + c7 * c7 * c4 * c4 + 2 * (c5 * c6 * c2 * c3 + c6 * c7 * c3 * c4 + c5 * c7 * c4 * c2) - c1 * (c2 * c2 + c3 * c3 + c4 * c4)
	if a == 0:
		print('{:.10f}'.format(-1 * (c / b)))
	else:
		zt = sqrt(b * b - 4 * a * c)
		zb = -1 * b
		ans1 = zb + zt
		ans1 /= 2 * a
		ans2 = zb - zt
		ans2 /= 2 * a
		l = [ans1, ans2]
		l.sort()
		if l[0] > 0:
			print('{:.10f}'.format(l[0]))
		else:
			print('{:.10f}'.format(l[1]))


epi = 10 ** (-2)

def vision(t):
	a1 = x0 + dx * t - x1
	a2 = y0 + dy * t - y1
	a3 = z0 + dz * t - z1
	b = 4 * (a1 * d1 + a2 * d2 + a3 * d3) * (a1 * d1 + a2 * d2 + a3 * d3)
	a = 4 * (a1 * a1 + a2 * a2 + a3 * a3)
	value = b - a * c
	return value
xrange = range
for _ in range(int(input())):
	(x1, y1, z1, x0, y0, z0, dx, dy, dz, cx, cy, cz, r) = list(map(int, input().split()))
	d1 = x1 - cx
	d2 = y1 - cy
	d3 = z1 - cz
	c = d1 * d1 + d2 * d2 + d3 * d3 - r * r
	low = 0
	high = 10 ** 9 + 1
	while low < high - 10 ** (-6):
		mid = low + (high - low) * 1.0 / 2
		value = vision(mid)
		if abs(value) <= epi:
			break
		elif value > 0:
			low = mid
		else:
			high = mid
	print(mid)


import math
for _ in range(int(input())):
	(a, b, c, e, f, g, e1, f1, g1, x1, y1, z1, k) = map(int, input().split())
	alp = a - x1
	bet = b - y1
	thet = c - z1
	c1 = 2 * e * e1 + 2 * f * f1 + 2 * g * g1 - 2 * a * e1 - 2 * b * f1 - 2 * c * g1
	c2 = e1 * e1 + f1 * f1 + g1 * g1
	c3 = 2 * alp * e1 + 2 * bet * f1 + 2 * thet * g1
	p = e * e + f * f + g * g - 2 * a * e - 2 * b * f - 2 * c * g + a * a + b * b + c * c
	q = 2 * e * alp + 2 * f * bet + 2 * g * thet - 2 * a * alp - 2 * b * bet - 2 * c * thet
	r = alp * alp + bet * bet + thet * thet - k * k
	X = c3 * c3 - 4 * c2 * r
	Y = 2 * q * c3 - 4 * c1 * r
	Z = q * q - 4 * p * r
	sq = float(math.sqrt(Y * Y - 4 * X * Z))
	if X != 0:
		ans1 = float((-Y - sq) / (2 * X))
		ans2 = float((-Y + sq) / (2 * X))
		if ans1 < 0 and ans2 >= 0:
			print('%.10f' % ans2)
		elif ans2 < 0 and ans1 >= 0:
			print('%.10f' % ans1)
		elif ans1 >= 0 and ans2 >= 0:
			print('%.10f' % min(ans1, ans2))
	else:
		print('%.10f' % float(-Z / Y))


import math
import numpy as np

def quadratic(a, b, c):
	if a == 0:
		x1 = -c / b
		x2 = 'undefined'
	else:
		d = b ** 2 - 4 * a * c
		if d > 0:
			x1 = (-b + math.sqrt(d)) / (2 * a)
			x2 = (-b - math.sqrt(d)) / (2 * a)
		elif d == 0:
			x1 = -b / (2 * a)
			x2 = x1
		else:
			(x1, x2) = ('i', 'i')
	return (x1, x2)

def solve_2_linear(a1, b1, c1, a2, b2, c2):
	a = np.array([[a1, b1], [a2, b2]])
	b = np.array([c1, c2])
	res = np.linalg.solve(a, b)
	return (res[0], res[1])
t = int(input())
for _ in range(t):
	line = list(map(int, input().split()))
	(Px, Py, Pz) = (line[0], line[1], line[2])
	(Qx, Qy, Qz) = (line[3], line[4], line[5])
	(Dx, Dy, Dz) = (line[6], line[7], line[8])
	(Cx, Cy, Cz) = (line[9], line[10], line[11])
	R = line[12]
	(X, Y, Z) = (Qx - Px, Qy - Py, Qz - Pz)
	(X2, Y2, Z2) = (X ** 2, Y ** 2, Z ** 2)
	(Dx2, Dy2, Dz2) = (Dx ** 2, Dy ** 2, Dz ** 2)
	(p, q, r) = (Px - Cx, Py - Cy, Pz - Cz)
	(p2, q2, r2) = (p ** 2, q ** 2, r ** 2)
	R2 = R ** 2
	a = r2 * Dy2 - 2 * r * q * Dy * Dz + q2 * Dz2 + p2 * Dz2 - 2 * r * p * Dx * Dz + r2 * Dx2 + q2 * Dx2 - 2 * p * q * Dx * Dy + p2 * Dy2 - R2 * (Dx2 + Dy2 + Dz2)
	b = 2 * r2 * Dy * Y - 2 * r * q * Dy * Z - 2 * r * q * Dz * Y + 2 * q2 * Dz * Z + 2 * p2 * Dz * Z - 2 * r * p * Dz * X - 2 * r * p * Dx * Z + 2 * r2 * Dx * X + 2 * q2 * Dx * X - 2 * p * q * Dx * Y - 2 * p * q * Dy * X + 2 * p2 * Dy * Y - 2 * R2 * (Dx * X + Dy * Y + Dz * Z)
	c = r2 * Y2 - 2 * r * q * Y * Z + q2 * Z2 + p2 * Z2 - 2 * r * p * Z * X + r2 * X2 + q2 * X2 - 2 * p * q * X * Y + p2 * Y2 - R2 * (X2 + Y2 + Z2)
	(t1, t2) = quadratic(a, b, c)
	if t2 == 'undefined':
		print(t1)
	elif t1 <= 0:
		print(t2)
	elif t2 <= 0:
		print(t1)
	else:
		print(min(t1, t2))


def snek(s):
	a1 = x0 + s1 * s - x1
	a2 = y0 + s2 * s - y1
	a3 = z0 + s3 * s - z1
	b = 4 * (a1 * d1 + a2 * d2 + a3 * d3) * (a1 * d1 + a2 * d2 + a3 * d3)
	a = 4 * (a1 * a1 + a2 * a2 + a3 * a3)
	v = b - a * c
	return v
t = int(input())
for i in range(t):
	(x1, y1, z1, x0, y0, z0, s1, s2, s3, cx, cy, cz, r) = map(int, input().split())
	d1 = x1 - cx
	d2 = y1 - cy
	d3 = z1 - cz
	c = d1 * d1 + d2 * d2 + d3 * d3 - r * r
	l = 0
	h = 10 ** 9 + 1
	while l < h - 10 ** (-6):
		m = l + (h - l) * 1.0 / 2
		v = snek(m)
		if abs(v) <= 10 ** (-2):
			break
		elif v > 0:
			l = m
		else:
			h = m
	print(m)


import math
TESTS = int(input())
for x in range(TESTS):
	a = input().split(' ')
	px = float(a[0])
	py = float(a[1])
	pz = float(a[2])
	qx = float(a[3])
	qy = float(a[4])
	qz = float(a[5])
	dx = float(a[6])
	dy = float(a[7])
	dz = float(a[8])
	cx = float(a[9])
	cy = float(a[10])
	cz = float(a[11])
	r = float(a[12])
	xx = dx * (px - cx) + dy * (py - cy) + dz * (pz - cz)
	yy = -px * (px - cx) - py * (py - cy) - pz * (pz - cz) + qx * (px - cx) + qy * (py - cy) + qz * (pz - cz)
	zz = xx * xx
	aa = 2 * xx * yy
	bb = yy * yy
	co = cx * cx + cy * cy + cz * cz + px * px + py * py + pz * pz - 2 * (cx * px + cy * py + cz * pz) - r * r
	rq2 = co * (dx * dx + dy * dy + dz * dz)
	rq1 = co * 2 * (dx * (qx - px) + dy * (qy - py) + dz * (qz - pz))
	rq0 = co * (qx - px) * (qx - px) + co * (qy - py) * (qy - py) + co * (qz - pz) * (qz - pz)
	q2 = zz - rq2
	q1 = aa - rq1
	q0 = bb - rq0
	yyyy = math.sqrt(1.0 * q1 * q1 - 4 * q2 * q0)
	if q2 == 0:
		ans = -q0 / q1
		print('%.20f' % ans)
	else:
		ans1 = (-q1 + math.sqrt(1.0 * q1 * q1 - 4 * q2 * q0)) / (1.0 * 2 * q2)
		ans2 = (-q1 - math.sqrt(1.0 * q1 * q1 - 4 * q2 * q0)) / (1.0 * 2 * q2)
		if ans2 * ans1 <= 0:
			ans = max(ans1, ans2)
		else:
			ans = min(ans1, ans2)
		print('%.20f' % ans)


import math
t = int(input())
for _ in range(t):
	(px, py, pz, qx0, qy0, qz0, dx, dy, dz, cx, cy, cz, r) = map(int, input().split())
	a = px - cx
	b = py - cy
	c = pz - cz
	x = px - qx0
	y = py - qy0
	z = pz - qz0
	(e1, e2, e3) = (b * z - c * y, a * z - c * x, a * y - b * x)
	(f1, f2, f3) = (c * dy - b * dz, dx * c - dz * a, dx * b - dy * a)
	a2 = f1 * f1 + f2 * f2 + f3 * f3
	b2 = 2 * (f1 * e1 + f2 * e2 + f3 * e3)
	c2 = e1 * e1 + e2 * e2 + e3 * e3
	c1 = x * x + y * y + z * z
	a1 = dx * dx + dy * dy + dz * dz
	b1 = -2 * (dx * x + dy * y + dz * z)
	g = a2 - a1 * r * r
	h = b2 - b1 * r * r
	i = c2 - c1 * r * r
	try:
		t1 = (-h + math.sqrt(h * h - 4 * g * i)) / (2 * g)
		t2 = (-h - math.sqrt(h * h - 4 * g * i)) / (2 * g)
		if t1 > 0 and t2 > 0:
			print(min(t1, t2))
		else:
			print(max(t1, t2))
	except:
		d = (cx - px) * (cx - px) + (cy - py) * (cy - py) + (cz - pz) * (cz - pz)
		f = 0
		for x in range(100):
			for y in range(100):
				for z in range(100):
					if (x - px) * (x - px) + (y - py) * (y - py) + (z - pz) * (z - pz) == d - r * r:
						f = 1
						break
				if f == 1:
					break
			if f == 1:
				break
		a = px - x
		b = py - y
		c = pz - z
		t = (b * (qx0 - px) - a * (qy0 - py)) / (a * dy - b * dx)
		print(t)


from math import *
coder = 'sdpt'
for _ in range(int(input())):
	arr = list(map(float, input().split()))
	p = arr[:3]
	q = arr[3:6]
	d = arr[6:9]
	c = arr[9:12]
	r = arr[12]
	m = [0] * 3
	n = [0] * 3
	for i in range(3):
		m[i] = c[i] - p[i]
		n[i] = q[i] - p[i]
	w = [0] * 3
	x = [0] * 3
	SumWsq = 0
	Sum2WX = 0
	SumXsq = 0
	SumNsq = 0
	Sum2ND = 0
	SumDsq = 0
	for i in range(3):
		j = (i + 1) % 3
		k = (i + 2) % 3
		w[i] = m[j] * n[k] - m[k] * n[j]
		x[i] = m[j] * d[k] - m[k] * d[j]
		SumWsq += w[i] * w[i]
		Sum2WX += 2 * w[i] * x[i]
		SumXsq += x[i] * x[i]
		SumNsq += n[i] * n[i] * r * r
		SumDsq += d[i] * d[i] * r * r
		Sum2ND += 2 * d[i] * n[i] * r * r
	A = SumXsq - SumDsq
	B = Sum2WX - Sum2ND
	C = SumWsq - SumNsq
	if A == 0:
		ans = -C / B
		print('%.8f' % ans)
	else:
		ans = (-B + sqrt(B * B - 4 * A * C)) / (2 * A)
		print('%.8f' % ans)


from math import sqrt
t = int(input())
for _ in range(t):
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(int, input().split())
	r = r - 1e-12
	nice = (2 * cy ** 2 * dx * px + 2 * cz ** 2 * dx * px - 2 * cx * cy * dy * px - 2 * cx * cz * dz * px + 2 * cy * dy * px ** 2 + 2 * cz * dz * px ** 2 - 2 * cx * cy * dx * py + 2 * cx ** 2 * dy * py + 2 * cz ** 2 * dy * py - 2 * cy * cz * dz * py - 2 * cy * dx * px * py - 2 * cx * dy * px * py + 2 * cx * dx * py ** 2 + 2 * cz * dz * py ** 2 - 2 * cx * cz * dx * pz - 2 * cy * cz * dy * pz + 2 * cx ** 2 * dz * pz + 2 * cy ** 2 * dz * pz - 2 * cz * dx * px * pz - 2 * cx * dz * px * pz - 2 * cz * dy * py * pz - 2 * cy * dz * py * pz + 2 * cx * dx * pz ** 2 + 2 * cy * dy * pz ** 2 - 2 * cy ** 2 * dx * qx - 2 * cz ** 2 * dx * qx + 2 * cx * cy * dy * qx + 2 * cx * cz * dz * qx - 2 * cy * dy * px * qx - 2 * cz * dz * px * qx + 4 * cy * dx * py * qx - 2 * cx * dy * py * qx + 2 * dy * px * py * qx - 2 * dx * py ** 2 * qx + 4 * cz * dx * pz * qx - 2 * cx * dz * pz * qx + 2 * dz * px * pz * qx - 2 * dx * pz ** 2 * qx + 2 * cx * cy * dx * qy - 2 * cx ** 2 * dy * qy - 2 * cz ** 2 * dy * qy + 2 * cy * cz * dz * qy - 2 * cy * dx * px * qy + 4 * cx * dy * px * qy - 2 * dy * px ** 2 * qy - 2 * cx * dx * py * qy - 2 * cz * dz * py * qy + 2 * dx * px * py * qy + 4 * cz * dy * pz * qy - 2 * cy * dz * pz * qy + 2 * dz * py * pz * qy - 2 * dy * pz ** 2 * qy + 2 * cx * cz * dx * qz + 2 * cy * cz * dy * qz - 2 * cx ** 2 * dz * qz - 2 * cy ** 2 * dz * qz - 2 * cz * dx * px * qz + 4 * cx * dz * px * qz - 2 * dz * px ** 2 * qz - 2 * cz * dy * py * qz + 4 * cy * dz * py * qz - 2 * dz * py ** 2 * qz - 2 * cx * dx * pz * qz - 2 * cy * dy * pz * qz + 2 * dx * px * pz * qz + 2 * dy * py * pz * qz - 2 * dx * px * r ** 2 - 2 * dy * py * r ** 2 - 2 * dz * pz * r ** 2 + 2 * dx * qx * r ** 2 + 2 * dy * qy * r ** 2 + 2 * dz * qz * r ** 2 + sqrt((-2 * cy ** 2 * dx * px - 2 * cz ** 2 * dx * px + 2 * cx * cy * dy * px + 2 * cx * cz * dz * px - 2 * cy * dy * px ** 2 - 2 * cz * dz * px ** 2 + 2 * cx * cy * dx * py - 2 * cx ** 2 * dy * py - 2 * cz ** 2 * dy * py + 2 * cy * cz * dz * py + 2 * cy * dx * px * py + 2 * cx * dy * px * py - 2 * cx * dx * py ** 2 - 2 * cz * dz * py ** 2 + 2 * cx * cz * dx * pz + 2 * cy * cz * dy * pz - 2 * cx ** 2 * dz * pz - 2 * cy ** 2 * dz * pz + 2 * cz * dx * px * pz + 2 * cx * dz * px * pz + 2 * cz * dy * py * pz + 2 * cy * dz * py * pz - 2 * cx * dx * pz ** 2 - 2 * cy * dy * pz ** 2 + 2 * cy ** 2 * dx * qx + 2 * cz ** 2 * dx * qx - 2 * cx * cy * dy * qx - 2 * cx * cz * dz * qx + 2 * cy * dy * px * qx + 2 * cz * dz * px * qx - 4 * cy * dx * py * qx + 2 * cx * dy * py * qx - 2 * dy * px * py * qx + 2 * dx * py ** 2 * qx - 4 * cz * dx * pz * qx + 2 * cx * dz * pz * qx - 2 * dz * px * pz * qx + 2 * dx * pz ** 2 * qx - 2 * cx * cy * dx * qy + 2 * cx ** 2 * dy * qy + 2 * cz ** 2 * dy * qy - 2 * cy * cz * dz * qy + 2 * cy * dx * px * qy - 4 * cx * dy * px * qy + 2 * dy * px ** 2 * qy + 2 * cx * dx * py * qy + 2 * cz * dz * py * qy - 2 * dx * px * py * qy - 4 * cz * dy * pz * qy + 2 * cy * dz * pz * qy - 2 * dz * py * pz * qy + 2 * dy * pz ** 2 * qy - 2 * cx * cz * dx * qz - 2 * cy * cz * dy * qz + 2 * cx ** 2 * dz * qz + 2 * cy ** 2 * dz * qz + 2 * cz * dx * px * qz - 4 * cx * dz * px * qz + 2 * dz * px ** 2 * qz + 2 * cz * dy * py * qz - 4 * cy * dz * py * qz + 2 * dz * py ** 2 * qz + 2 * cx * dx * pz * qz + 2 * cy * dy * pz * qz - 2 * dx * px * pz * qz - 2 * dy * py * pz * qz + 2 * dx * px * r ** 2 + 2 * dy * py * r ** 2 + 2 * dz * pz * r ** 2 - 2 * dx * qx * r ** 2 - 2 * dy * qy * r ** 2 - 2 * dz * qz * r ** 2) ** 2 - 4 * (cy ** 2 * dx ** 2 + cz ** 2 * dx ** 2 - 2 * cx * cy * dx * dy + cx ** 2 * dy ** 2 + cz ** 2 * dy ** 2 - 2 * cx * cz * dx * dz - 2 * cy * cz * dy * dz + cx ** 2 * dz ** 2 + cy ** 2 * dz ** 2 + 2 * cy * dx * dy * px - 2 * cx * dy ** 2 * px + 2 * cz * dx * dz * px - 2 * cx * dz ** 2 * px + dy ** 2 * px ** 2 + dz ** 2 * px ** 2 - 2 * cy * dx ** 2 * py + 2 * cx * dx * dy * py + 2 * cz * dy * dz * py - 2 * cy * dz ** 2 * py - 2 * dx * dy * px * py + dx ** 2 * py ** 2 + dz ** 2 * py ** 2 - 2 * cz * dx ** 2 * pz - 2 * cz * dy ** 2 * pz + 2 * cx * dx * dz * pz + 2 * cy * dy * dz * pz - 2 * dx * dz * px * pz - 2 * dy * dz * py * pz + dx ** 2 * pz ** 2 + dy ** 2 * pz ** 2 - dx ** 2 * r ** 2 - dy ** 2 * r ** 2 - dz ** 2 * r ** 2) * (cy ** 2 * px ** 2 + cz ** 2 * px ** 2 - 2 * cx * cy * px * py + cx ** 2 * py ** 2 + cz ** 2 * py ** 2 - 2 * cx * cz * px * pz - 2 * cy * cz * py * pz + cx ** 2 * pz ** 2 + cy ** 2 * pz ** 2 - 2 * cy ** 2 * px * qx - 2 * cz ** 2 * px * qx + 2 * cx * cy * py * qx + 2 * cy * px * py * qx - 2 * cx * py ** 2 * qx + 2 * cx * cz * pz * qx + 2 * cz * px * pz * qx - 2 * cx * pz ** 2 * qx + cy ** 2 * qx ** 2 + cz ** 2 * qx ** 2 - 2 * cy * py * qx ** 2 + py ** 2 * qx ** 2 - 2 * cz * pz * qx ** 2 + pz ** 2 * qx ** 2 + 2 * cx * cy * px * qy - 2 * cy * px ** 2 * qy - 2 * cx ** 2 * py * qy - 2 * cz ** 2 * py * qy + 2 * cx * px * py * qy + 2 * cy * cz * pz * qy + 2 * cz * py * pz * qy - 2 * cy * pz ** 2 * qy - 2 * cx * cy * qx * qy + 2 * cy * px * qx * qy + 2 * cx * py * qx * qy - 2 * px * py * qx * qy + cx ** 2 * qy ** 2 + cz ** 2 * qy ** 2 - 2 * cx * px * qy ** 2 + px ** 2 * qy ** 2 - 2 * cz * pz * qy ** 2 + pz ** 2 * qy ** 2 + 2 * cx * cz * px * qz - 2 * cz * px ** 2 * qz + 2 * cy * cz * py * qz - 2 * cz * py ** 2 * qz - 2 * cx ** 2 * pz * qz - 2 * cy ** 2 * pz * qz + 2 * cx * px * pz * qz + 2 * cy * py * pz * qz - 2 * cx * cz * qx * qz + 2 * cz * px * qx * qz + 2 * cx * pz * qx * qz - 2 * px * pz * qx * qz - 2 * cy * cz * qy * qz + 2 * cz * py * qy * qz + 2 * cy * pz * qy * qz - 2 * py * pz * qy * qz + cx ** 2 * qz ** 2 + cy ** 2 * qz ** 2 - 2 * cx * px * qz ** 2 + px ** 2 * qz ** 2 - 2 * cy * py * qz ** 2 + py ** 2 * qz ** 2 - px ** 2 * r ** 2 - py ** 2 * r ** 2 - pz ** 2 * r ** 2 + 2 * px * qx * r ** 2 - qx ** 2 * r ** 2 + 2 * py * qy * r ** 2 - qy ** 2 * r ** 2 + 2 * pz * qz * r ** 2 - qz ** 2 * r ** 2))) / (2.0 * (cy ** 2 * dx ** 2 + cz ** 2 * dx ** 2 - 2 * cx * cy * dx * dy + cx ** 2 * dy ** 2 + cz ** 2 * dy ** 2 - 2 * cx * cz * dx * dz - 2 * cy * cz * dy * dz + cx ** 2 * dz ** 2 + cy ** 2 * dz ** 2 + 2 * cy * dx * dy * px - 2 * cx * dy ** 2 * px + 2 * cz * dx * dz * px - 2 * cx * dz ** 2 * px + dy ** 2 * px ** 2 + dz ** 2 * px ** 2 - 2 * cy * dx ** 2 * py + 2 * cx * dx * dy * py + 2 * cz * dy * dz * py - 2 * cy * dz ** 2 * py - 2 * dx * dy * px * py + dx ** 2 * py ** 2 + dz ** 2 * py ** 2 - 2 * cz * dx ** 2 * pz - 2 * cz * dy ** 2 * pz + 2 * cx * dx * dz * pz + 2 * cy * dy * dz * pz - 2 * dx * dz * px * pz - 2 * dy * dz * py * pz + dx ** 2 * pz ** 2 + dy ** 2 * pz ** 2 - dx ** 2 * r ** 2 - dy ** 2 * r ** 2 - dz ** 2 * r ** 2))
	print(nice)


from math import *
T = int(input())
for i in range(T):
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = list(map(int, input().split(' ')))
	(p1x, p2x) = (cx - px, qx - px)
	(p1y, p2y) = (cy - py, qy - py)
	(p1z, p2z) = (cz - pz, qz - pz)
	usel = p1x * p1x + p1y * p1y + p1z * p1z - r ** 2
	dot1 = 2 * ((p2x * dx + p2y * dy + p2z * dz) * usel - (dx * p1x + dy * p1y + dz * p1z) * (p1x * p2x + p1y * p2y + p1z * p2z))
	dot2 = (dx * dx + dy * dy + dz * dz) * usel - (dx * p1x + dy * p1y + dz * p1z) * (dx * p1x + dy * p1y + dz * p1z)
	dot3 = (p2x * p2x + p2y * p2y + p2z * p2z) * usel - (p2x * p1x + p2y * p1y + p2z * p1z) * (p2x * p1x + p2y * p1y + p2z * p1z)
	determ = sqrt(dot1 * dot1 - 4 * dot2 * dot3)
	tn = 0
	tm = 0
	tn = -dot1 + determ
	tm = -dot1 - determ
	if dot2 != 0:
		tn = tn / (2 * dot2)
		tm = tm / (2 * dot2)
		if tn > 0 and tm > 0:
			t = min(tn, tm)
			print('%.10f' % t)
		elif tn > 0 and tm < 0:
			t = tn
			print('%.10f' % t)
		elif tn < 0 and tm > 0:
			t = tm
			print('%.10f' % t)
	else:
		t = -dot3 / dot1
		print('%.10f' % t)


import math
T = int(input())
while T > 0:
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = list(map(int, input().split()))
	X = px - cx
	Y = py - cy
	Z = pz - cz
	x = dx
	y = dy
	z = dz
	alpha = r * r - Z * Z - Y * Y
	beta = r * r - X * X - Z * Z
	gamma = r * r - X * X - Y * Y
	A = 2 * X * Y
	B = 2 * Y * Z
	C = 2 * X * Z
	qx = qx - px
	qy = qy - py
	qz = qz - pz
	a = alpha * x * x + beta * y * y + gamma * z * z + A * x * y + B * y * z + C * x * z
	b = 2 * alpha * x * qx + 2 * beta * y * qy + 2 * gamma * z * qz + A * (y * qx + x * qy) + B * (z * qy + y * qz) + C * (z * qx + x * qz)
	k = alpha * qx * qx + beta * qy * qy + gamma * qz * qz + A * qx * qy + B * qy * qz + C * qx * qz
	discrim = b * b - 4 * a * k
	ans = 0
	if a == 0:
		ans = -1 * k / b
	else:
		ans = (-1 * b - math.sqrt(discrim)) / (2 * a)
		if ans <= 0:
			ans = (-1 * b + math.sqrt(discrim)) / (2 * a)
	print('%.6f' % ans)
	T = T - 1


from math import sqrt
test = int(input())
for i in range(test):
	(x2, y2, z2, x3, y3, z3, d1, d2, d3, a, b, c, r) = map(int, input().split())
	k = x2 - x3
	l = y2 - y3
	m = z2 - z3
	k1 = (x2 - a) * (x2 - a) + (y2 - b) * (y2 - b) + (z2 - c) * (z2 - c) - r * r
	so = d2 * (y2 - b) + d3 * (z2 - c) + d1 * (x2 - a)
	lo = k * (x2 - a) + l * (y2 - b) + m * (z2 - c)
	zz = lo * lo - k1 * (k * k + l * l + m * m)
	don = d1 * d1 + d2 * d2 + d3 * d3
	xx = so * so - k1 * don
	ron = x2 * y2 * z2 * don
	kon = don * x2
	tyui = don * don
	yy = -2 * lo * so + k1 * 2 * (k * d1 + l * d2 + m * d3)
	pui = ron * xx
	dfg = xx * yy
	if xx == 0:
		print(zz / -yy + 1e-07)
	else:
		ans1 = (-yy + sqrt(yy ** 2 - 4 * xx * zz)) / (2 * xx)
		ans2 = (-yy - sqrt(yy ** 2 - 4 * xx * zz)) / (2 * xx)
		if ans2 > 0:
			print(ans2 + 1e-07)
		else:
			print(ans1 + 1e-07)


import math
w = int(input())
while w > 0:
	w = w - 1
	h = map(int, input().split(' '))
	h = list(h)
	px = h[0]
	py = h[1]
	pz = h[2]
	qx = h[3]
	qy = h[4]
	qz = h[5]
	dx = h[6]
	dy = h[7]
	dz = h[8]
	cx = h[9]
	cy = h[10]
	cz = h[11]
	r = h[12]
	x = (qx - px) * (px - cx) + (qy - py) * (py - cy) + (qz - pz) * (pz - cz)
	y = (px - cx) * dx + (py - cy) * dy + (pz - cz) * dz
	z = (qx - px) * (qx - px) + (qy - py) * (qy - py) + (qz - pz) * (qz - pz)
	x1 = 2 * (qx - px) * dx + 2 * (qy - py) * dy + 2 * (qz - pz) * dz
	x2 = dx * dx + dy * dy + dz * dz
	x3 = (px - cx) * (px - cx) + (py - cy) * (py - cy) + (pz - cz) * (pz - cz)
	b = 2 * x * y + r * r * x1 - x3 * x1
	c = x * x + r * r * z - x3 * z
	a = y * y + r * r * x2 - x3 * x2
	x = b * b - 4 * a * c
	D = math.pow(x, 1 / 2)
	if a == 0:
		r1 = -(c / b)
		r2 = r1
	else:
		r1 = (-b - D) / (2 * a)
		r2 = (b + D) / (2 * a)
	if r1 < 0:
		r1 = -r1
	if r2 < 0:
		r2 = -r2
	print(r1)


t = int(input())
for i in range(t):
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = [float(x) for x in input().split()]
	a = cx - px
	b = cy - py
	c = cz - pz
	d = qx - px
	e = qy - py
	f = qz - pz
	A = r * r * (dx * dx + dy * dy + dz * dz) - ((a * dy - b * dx) ** 2 + (b * dz - c * dy) ** 2 + (c * dx - a * dz) ** 2)
	tb1 = 2 * r * r * (dx * d + dy * e + dz * f)
	asq = a * a
	bsq = b * b
	csq = c * c
	dsq = d * d
	esq = e * e
	fsq = f * f
	absq = asq + bsq
	bcsq = bsq + csq
	acsq = asq + csq
	cf = c * f
	be = b * e
	ad = a * d
	tb2 = 2 * (dx * (a * (cf + be) - d * bcsq) + dy * (b * (cf + ad) - e * acsq) + dz * (c * (be + ad) - f * absq))
	B = tb1 + tb2
	tc1 = r * r * (dsq + esq + fsq) - absq * fsq - acsq * esq - bcsq * dsq
	C = tc1 + 2 * (be * cf + ad * cf + ad * be)
	if A == 0:
		t = -1 * (C / B)
		print(t)
	else:
		t1 = (-B + (B * B - 4 * A * C) ** 0.5) / (2 * A)
		t2 = (-B - (B * B - 4 * A * C) ** 0.5) / (2 * A)
		if t1 < 0:
			print(t2)
		elif t2 < 0:
			print(t1)
		else:
			print(min(t1, t2))


import math
T = int(input())
for t in range(T):
	s = input().split()
	p1 = float(s[0])
	p2 = float(s[1])
	p3 = float(s[2])
	q1 = float(s[3])
	q2 = float(s[4])
	q3 = float(s[5])
	d1 = float(s[6])
	d2 = float(s[7])
	d3 = float(s[8])
	c1 = float(s[9])
	c2 = float(s[10])
	c3 = float(s[11])
	r = float(s[12])
	ai = q2 * p3 - q2 * c3 + p2 * c3 - p2 * q3 + c2 * q3 - c2 * p3
	bi = d2 * p3 - d2 * c3 - p2 * d3 + c2 * d3
	aj = -q1 * p3 + c3 * q1 - c3 * p1 + p1 * q3 - c1 * q3 + c1 * p3
	bj = -p3 * d1 + c3 * d1 + p1 * d3 - c1 * d3
	ak = p2 * q1 - c2 * q1 + c2 * p1 - p1 * q2 + c1 * q2 - c1 * p2
	bk = p2 * d1 - c2 * d1 - p1 * d2 + c1 * d2
	flag1 = 0
	snk1 = ai * ai + aj * aj + ak * ak
	snk2 = bi * bi + bj * bj + bk * bk
	snk3 = 2 * ai * bi + 2 * aj * bj + 2 * ak * bk
	ci = q1 - p1
	cj = q2 - p2
	ck = q3 - p3
	aa1 = ci * ci + cj * cj + ck * ck
	aa2 = d1 * d1 + d2 * d2 + d3 * d3
	aa3 = 2 * ci * d1 + 2 * cj * d2 + 2 * ck * d3
	flag2 = 0
	c1 = snk2 - r * r * aa2
	c2 = snk3 - r * r * aa3
	c3 = snk1 - r * r * aa1
	if c1 != 0:
		flag1 = 1
		ans1 = (-c2 + math.sqrt(c2 * c2 - 4 * c1 * c3)) / (2 * c1)
		ans2 = (-c2 - math.sqrt(c2 * c2 - 4 * c1 * c3)) / (2 * c1)
		if ans1 > 0 and ans2 > 0:
			if ans1 < ans2:
				ans = ans1
			else:
				ans = ans2
		elif ans1 > 0:
			ans = ans1
		else:
			ans = ans2
	else:
		flag2 = 1
		ans = -c3 / c2
	print(ans)


import math
T = int(input())
for v in range(T):
	arr = inp = list(map(int, input().split()))
	x1 = arr[0]
	y1 = arr[1]
	z1 = arr[2]
	x3 = arr[3]
	y3 = arr[4]
	z3 = arr[5]
	dx = arr[6]
	dy = arr[7]
	dz = arr[8]
	x0 = arr[9]
	y0 = arr[10]
	z0 = arr[11]
	r = arr[12]
	a = x0 - x1
	b = y0 - y1
	c = z0 - z1
	k1 = b * (z0 - z3) - c * (y0 - y3)
	k2 = c * (x0 - x3) - a * (z0 - z3)
	k3 = a * (y0 - y3) - b * (x0 - x3)
	f1 = b * dz - c * dy
	f2 = c * dx - a * dz
	f3 = a * dy - b * dx
	l1 = x3 - x1
	l2 = y3 - y1
	l3 = z3 - z1
	j = f1 ** 2 + f2 ** 2 + f3 ** 2 - r ** 2 * (dx ** 2 + dy ** 2 + dz ** 2)
	k = k1 * f1 + k2 * f2 + k3 * f3 + (dx * l1 + dy * l2 + dz * l3) * r ** 2
	l = k1 ** 2 + k2 ** 2 + k3 ** 2 - (l1 ** 2 + l2 ** 2 + l3 ** 2) * r ** 2
	disc = math.sqrt(k ** 2 - l * j)
	if j != 0:
		r1 = (k + disc) / j
		r2 = (k - disc) / j
		if r1 > 0:
			print(r1)
		if r2 > 0:
			print(r2)
	else:
		ans = l / (2 * k)
		print(ans)


import math
t = int(input())
while t > 0:
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(float, input().split())
	temp = (px - cx) ** 2 + (py - cy) ** 2 + (pz - cz) ** 2
	a1 = -temp + r ** 2 + (px - cx) ** 2
	a2 = -temp + r ** 2 + (py - cy) ** 2
	a3 = -temp + r ** 2 + (pz - cz) ** 2
	b1 = qx - px
	b2 = qy - py
	b3 = qz - pz
	c1 = px - cx
	c2 = py - cy
	c3 = pz - cz
	A = a1 * dx ** 2 + a2 * dy ** 2 + a3 * dz ** 2 + 2 * (dx * dy * c1 * c2) + 2 * (dz * dy * c2 * c3) + 2 * (dx * dz * c3 * c1)
	B = 2 * a1 * b1 * dx + 2 * a2 * b2 * dy + 2 * a3 * b3 * dz + 2 * c1 * b1 * c2 * dy + 2 * c1 * b2 * c2 * dx + 2 * c1 * b1 * c3 * dz + 2 * c1 * b3 * c3 * dx + 2 * c3 * b3 * c2 * dy + 2 * c3 * b2 * c2 * dz
	C = a1 * b1 ** 2 + a2 * b2 ** 2 + a3 * b3 ** 2 + 2 * c1 * b1 * b2 * c2 + 2 * c2 * b2 * b3 * c3 + 2 * c3 * b1 * b3 * c1
	D = B ** 2 - 4 * A * C
	if A != 0:
		t1 = (-B + math.sqrt(D)) / (2 * A)
		t2 = (-B - math.sqrt(D)) / (2 * A)
		if t1 > 0 and t2 < 0:
			print(t1)
		elif t2 > 0 and t1 < 0:
			print(t2)
		else:
			print(max(t1, t2))
	elif A == 0:
		print(-C / B)
	t -= 1


from math import *

def sq(n):
	return n * n
k = int(input())
while k:
	mp = input().split()
	px = int(mp[0])
	py = int(mp[1])
	pz = int(mp[2])
	qx = int(mp[3])
	qy = int(mp[4])
	qz = int(mp[5])
	dx = int(mp[6])
	dy = int(mp[7])
	dz = int(mp[8])
	cx = int(mp[9])
	cy = int(mp[10])
	cz = int(mp[11])
	r = int(mp[12])
	x2 = px
	y2 = py
	z2 = pz
	x0 = qx
	y0 = qy
	z0 = qz
	a11 = x2 - x0
	a22 = y2 - y0
	a33 = z2 - z0
	b11 = -dx
	b22 = -dy
	b33 = -dz
	x = x2 - cx
	y = y2 - cy
	z = z2 - cz
	A = y * z2 - z * y2
	B = z * x2 - x * z2
	C = x * y2 - y * x2
	a1 = A - y * z0 + z * y0
	a2 = B - z * x0 + x * z0
	a3 = C - x * y0 + y * x0
	b1 = z * dy - y * dz
	b2 = x * dz - z * dx
	b3 = y * dx - x * dy
	a = sq(b11) * sq(r) - sq(b1) + sq(b22) * sq(r) - sq(b2) + sq(b33) * sq(r) - sq(b3)
	b = 2 * (a11 * b11 * sq(r) - a1 * b1) + 2 * (a22 * b22 * sq(r) - a2 * b2) + 2 * (a33 * b33 * sq(r) - a3 * b3)
	c = sq(a11) * sq(r) - sq(a1) + sq(a22) * sq(r) - sq(a2) + sq(a33) * sq(r) - sq(a3)
	if a == 0:
		print(-c / b)
		k -= 1
		continue
	k1 = (-b + sqrt(b * b - 4 * a * c)) / 2 / a
	k2 = (-b - sqrt(b * b - 4 * a * c)) / 2 / a
	if k1 >= 0.0 and k2 >= 0.0:
		print(min(k1, k2))
	elif k1 >= 0.0:
		print(k1)
	elif k2 >= 0.0:
		print(k2)
	k -= 1


def isSeen(x, y, z, Cx, Cy, Cz, CP2, R):
	a = x * Cx + y * Cy + z * Cz
	b = x * x + y * y + z * z
	return CP2 * b - a * a > R * R * b
N = int(input())
for t in range(N):
	(Px, Py, Pz, Qx, Qy, Qz, dx, dy, dz, Cx, Cy, Cz, R) = [int(i) for i in input().split()]
	Qx = Qx - Px
	Qy = Qy - Py
	Qz = Qz - Pz
	Cx = Cx - Px
	Cy = Cy - Py
	Cz = Cz - Pz
	CP2 = Cx * Cx + Cy * Cy + Cz * Cz
	l = 0
	h = 1100000000.0
	m = (l + h) / 2
	while h - l >= 1e-07:
		if isSeen(Qx + m * dx, Qy + m * dy, Qz + m * dz, Cx, Cy, Cz, CP2, R):
			h = m
		else:
			l = m
		m = (l + h) / 2
	print(m)


def dot(a, b):
	r1 = a[0] * b[0]
	r2 = a[1] * b[1]
	r3 = a[2] * b[2]
	r = r1 + r2 + r3
	return r
for i in range(int(input())):
	(x1, y1, z1, x2, y2, z2, d1, d2, d3, c1, c2, c3, r) = map(float, input().split())
	t1 = r ** 2 * d1 ** 2 + r ** 2 * d2 ** 2 + r ** 2 * d3 ** 2
	t2 = (d1 * (y1 - c2) - d2 * (x1 - c1)) ** 2 + (d2 * (z1 - c3) - d3 * (y1 - c2)) ** 2 + (d3 * (x1 - c1) - d1 * (z1 - c3)) ** 2
	A = t1 - t2
	t11 = 2 * r ** 2 * ((x2 - x1) * d1 + (y2 - y1) * d2 + (z2 - z1) * d3)
	t22 = 2 * (((x2 - x1) * (y1 - c2) - (y2 - y1) * (x1 - c1)) * (d1 * (y1 - c2) - d2 * (x1 - c1)) + ((y2 - y1) * (z1 - c3) - (z2 - z1) * (y1 - c2)) * (d2 * (z1 - c3) - d3 * (y1 - c2)) + ((z2 - z1) * (x1 - c1) - (x2 - x1) * (z1 - c3)) * (d3 * (x1 - c1) - d1 * (z1 - c3)))
	B = t11 - t22
	t111 = r ** 2 * ((x2 - x1) ** 2 + (y2 - y1) ** 2 + (z2 - z1) ** 2)
	t222 = ((x2 - x1) * (y1 - c2) - (y2 - y1) * (x1 - c1)) ** 2 + ((y2 - y1) * (z1 - c3) - (z2 - z1) * (y1 - c2)) ** 2 + ((z2 - z1) * (x1 - c1) - (x2 - x1) * (z1 - c3)) ** 2
	C = t111 - t222
	if A != 0:
		Z = 2 * A
		t1 = (-1 * B + (B ** 2 - 4 * A * C) ** 0.5) / Z
		t2 = (-1 * B - (B ** 2 - 4 * A * C) ** 0.5) / Z
		t = 0
		q = 0
		if t2 < q:
			t = t1
		elif t1 < q:
			t = t2
		elif t1 >= q and t2 >= q:
			if t1 > t2:
				t = t2
			elif t2 > t1:
				t = t1
		print('%.10f' % t)
	elif A == 0:
		t = -1 * C / B
		print('%.10f' % t)
		continue


import math

def twice(n):
	a = n * n
	return a

class data:
	locx = 0.0
	locy = 0.0
	locz = 0.0

	def subtract(first, second):
		variable2 = data()
		variable2.locx = first.locx - second.locx
		variable2.locy = first.locy - second.locy
		variable2.locz = first.locz - second.locz
		return variable2
ashu = input()
ashu = int(ashu)
for testcases in range(1, ashu + 1):
	variable1 = data()
	variable2 = data()
	d = data()
	c = data()
	medium = input().split(' ')
	variable1.locx = float(medium[0])
	variable1.locy = float(medium[1])
	variable1.locz = float(medium[2])
	variable2.locx = float(medium[3])
	variable2.locy = float(medium[4])
	variable2.locz = float(medium[5])
	d.locx = float(medium[6])
	d.locy = float(medium[7])
	d.locz = float(medium[8])
	c.locx = float(medium[9])
	c.locy = float(medium[10])
	c.locz = float(medium[11])
	r = float(medium[12])
	palak1 = math.sqrt(twice(c.locx - variable1.locx) + twice(c.locy - variable1.locy) + twice(c.locz - variable1.locz))
	palak2 = r / palak1
	palak3 = math.sqrt(1 - twice(palak2))
	palak4 = data()
	palak5 = data()
	palak4 = c.subtract(variable1)
	palak5 = variable2.subtract(variable1)
	palak6 = palak4.locx * palak5.locx + palak4.locy * palak5.locy + palak4.locz * palak5.locz
	palak7 = palak4.locx * d.locx + palak4.locy * d.locy + palak4.locz * d.locz
	palak8 = math.sqrt(twice(palak4.locx) + twice(palak4.locy) + twice(palak4.locz))
	palak9 = twice(palak8) * twice(palak3)
	palak10 = math.sqrt(twice(palak5.locx) + twice(palak5.locy) + twice(palak5.locz))
	palak11 = math.sqrt(twice(d.locx) + twice(d.locy) + twice(d.locz))
	palak12 = palak5.locx * d.locx + palak5.locy * d.locy + palak5.locz * d.locz
	palak16 = twice(palak11) - twice(palak7) / palak9
	palak17 = 2 * (palak12 - palak6 * palak7 / palak9)
	palak18 = twice(palak10) - twice(palak6) / palak9
	if palak16 < 10 ** (-10):
		answeris = -1.0 * palak18 / palak17
	else:
		palak13 = math.sqrt(twice(palak17) - 4 * palak16 * palak18)
		palak14 = (palak13 - palak17) / (2 * palak16)
		palak15 = (-palak13 - palak17) / (2 * palak16)
		if palak15 < 0 or palak14 < 0:
			answeris = max(palak15, palak14)
		else:
			answeris = min(palak15, palak14)
	print(answeris)


import math
t = int(input())
while t > 0:
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = list(map(int, input().split()))
	x = cx - px
	y = cy - py
	z = cz - pz
	lm = x ** 2 + y ** 2 + z ** 2 - r ** 2
	xx = qx - px
	yy = qy - py
	zz = qz - pz
	dxyz = dx * x + dy * y + dz * z
	xyz = xx * x + yy * y + zz * z
	A = (dx ** 2 + dy ** 2 + dz ** 2) * lm - dxyz ** 2
	B = 2 * ((dx * xx + dy * yy + dz * zz) * lm - dxyz * xyz)
	C = (xx ** 2 + yy ** 2 + zz ** 2) * lm - xyz ** 2
	if A == 0:
		ans = -C / B
	else:
		ans1 = -B / (2 * A) + math.sqrt(B ** 2 - 4 * A * C) / (2 * A)
		ans2 = -B / (2 * A) - math.sqrt(B ** 2 - 4 * A * C) / (2 * A)
		if ans1 < 0:
			ans = ans2
		elif ans2 < 0:
			ans = ans1
		elif ans1 > 0 and ans2 > 0:
			ans = min(ans1, ans2)
		else:
			ans = -1
	print('{:.12f}'.format(ans))
	t = t - 1


import math
import sys
t = int(input())
while t > 0:
	(px, py, pz, qx, qy, qz, d1, d2, d3, cx, cy, cz, r) = map(int, input().strip().split())
	a1 = qx - px
	a2 = qy - py
	a3 = qz - pz
	a = cx - px
	b = cy - py
	c = cz - pz
	k = a1 * a + a2 * b + a3 * c
	h = a * d1 + b * d2 + c * d3
	g2 = a * a - r * r + b * b + c * c
	c1 = (a1 * d1 + a2 * d2 + a3 * d3) * g2 * 2
	c2 = g2 * (a1 * a1 + a2 * a2 + a3 * a3)
	a = h * h - g2 * (d1 * d1 + d2 * d2 + d3 * d3)
	b = 2 * h * k - c1
	c = k * k - c2
	if a == 0:
		x1 = -c / b
		print(x1)
		t -= 1
		continue
	discriminant = b * b - 4 * a * c
	x1 = (-b + math.sqrt(discriminant)) / (2 * a)
	x2 = (-b - math.sqrt(discriminant)) / (2 * a)
	if x1 > x2:
		print(x1)
	else:
		print(x2)
	t -= 1


import math
for _ in range(int(input())):
	l = [int(i) for i in input().split()]
	(use1, use2, use3, use4, use5, use6) = (0, 0, -l[12] * l[12], 0, 0, 0)
	for i in range(3):
		use1 = use1 + (l[i] - l[i + 3]) * (l[i] - l[i + 9])
		use2 = use2 + (l[i] - l[i + 9]) * l[i + 6]
		use3 = use3 + (l[i] - l[i + 9]) * (l[i] - l[i + 9])
		use4 = use4 + l[i + 6] * l[i + 6]
		use5 = use5 + (l[i + 3] - l[i]) * l[i + 6]
		use6 = use6 + (l[i + 3] - l[i]) * (l[i + 3] - l[i])
	a = 4 * use2 * use2 - 4 * use3 * use4
	b = 8 * use1 * use2 + 8 * use3 * use5
	c = 4 * use1 * use1 - 4 * use3 * use6
	desc = math.sqrt(b * b - 4 * a * c)
	if a == 0:
		k = c / b
		print('%.10f' % k)
	else:
		sol1 = (b + desc) / (2 * a)
		sol2 = (b - desc) / (2 * a)
		if sol1 > 0 and sol2 > 0:
			k = min(sol1, sol2)
			print('%.10f' % k)
		elif sol2 <= 0:
			print('%.10f' % sol1)
		elif sol1 <= 0:
			print('%.10f' % sol2)


import math
for t in range(int(input())):
	r = 0
	inp = [int(i) for i in input().split()]
	c = inp[9:12]
	p = inp[0:3]
	q = inp[3:6]
	d = inp[6:9]
	r = inp[12]
	A = B = D = E = F = S = 0
	for i in range(3):
		D += d[i] * d[i]
		E += 2 * (d[i] * (q[i] - p[i]))
		F += (q[i] - p[i]) ** 2
		A += d[i] * (c[i] - p[i])
		B += (q[i] - p[i]) * (c[i] - p[i])
		S += (c[i] - p[i]) ** 2
	S -= r ** 2
	FA = A ** 2 - D * S
	FB = 2 * A * B - E * S
	FC = B ** 2 - F * S
	if FA == 0:
		print(-FC / FB)
	else:
		dlt = (FB ** 2 - 4 * FA * FC) ** (1 / 2)
		t = max((-FB - dlt) / (2 * FA), (-FB + dlt) / (2 * FA))
		print(t)


T = int(input())
all = []
for i in range(0, T):
	all = [int(i) for i in input().split()]
	if (all[2] == 0 and all[5] == 0) and (all[8] == 0 and all[11] == 0):
		list1 = []
		list1.append(all[9] ** 2 + all[0] ** 2 - all[12] ** 2 - 2 * all[9] * all[0])
		list1.append(2 * (all[9] * all[1] + all[0] * all[10] - (all[9] * all[10] + all[0] * all[1])))
		list1.append(all[10] ** 2 + all[1] ** 2 - 2 * all[1] * all[10] - all[12] ** 2)
		x = all[0] - all[3]
		y = all[1] - all[4]
		a = list1[0] * (all[7] * all[7]) + list1[1] * all[6] * all[7] + list1[2] * (all[6] * all[6])
		b = 2 * list1[0] * y * all[7] + y * all[6] * list1[1] + list1[1] * x * all[7] + 2 * x * list1[2] * all[6]
		c = list1[0] * y ** 2 + list1[1] * x * y + list1[2] * x ** 2
		if a == 0 and (c != 0 and b != 0):
			print(c / b)
		elif b == 0:
			if c > 0 and a < 0 or (a > 0 and c < 0):
				print((c / a) ** 0.5)
		else:
			diff = b ** 2 - 4 * a * c
			if diff > 0:
				root1 = (b + diff ** 0.5) / (2 * a)
				root2 = (b - diff ** 0.5) / (2 * a)
				if root1 > 0 and root2 > 0:
					print(min(root1, root2))
				elif root1 > 0 and root2 < 0:
					print(root1)
				elif root1 < 0 and root2 > 0:
					print(root2)
			elif d == 0:
				root1 = (b + diff ** 0.5) / (2 * a)
				print(root1)
	else:
		P = []
		Q = []
		D = []
		C = []
		P.append(all[0])
		P.append(all[1])
		P.append(all[2])
		Q.append(all[3])
		Q.append(all[4])
		Q.append(all[5])
		D.append(all[6])
		D.append(all[7])
		D.append(all[8])
		C.append(all[9])
		C.append(all[10])
		C.append(all[11])
		C.append(all[12])
		side = (P[0] - C[0]) * (P[0] - C[0]) + (P[1] - C[1]) * (P[1] - C[1]) + (P[2] - C[2]) * (P[2] - C[2]) - C[3] * C[3]
		m = P[0] * P[0] + P[1] * P[1] + P[2] * P[2] - C[0] * C[0] - C[1] * C[1] - C[2] * C[2] + C[3] * C[3] - side - 2 * P[0] * Q[0] - 2 * P[1] * Q[1] - 2 * P[2] * Q[2] + 2 * C[0] * Q[0] + 2 * C[1] * Q[1] + 2 * C[2] * Q[2]
		n = 2 * C[0] * D[0] + 2 * C[1] * D[1] + 2 * C[2] * D[2] - 2 * P[0] * D[0] - 2 * P[1] * D[1] - 2 * P[2] * D[2]
		a = n * n - 4 * side * (D[0] * D[0] + D[1] * D[1] + D[2] * D[2])
		b = 2 * (-m * n + 4 * side * (D[0] * (Q[0] - C[0]) + D[1] * (Q[1] - C[1]) + D[2] * (Q[2] - C[2])))
		c = m * m + 4 * side * C[3] * C[3] - 4 * side * ((Q[0] - C[0]) * (Q[0] - C[0]) + (Q[1] - C[1]) * (Q[1] - C[1]) + (Q[2] - C[2]) * (Q[2] - C[2]))
		d = b * b - 4 * a * c
		if a == 0 and (b != 0 and c != 0):
			print(c / b)
		elif b == 0:
			if c > 0 and a < 0 or (a > 0 and c < 0):
				print((c / a) ** 0.5)
		elif d > 0:
			diff = d ** 0.5
			root1 = (b + diff) / (2 * a)
			root2 = (b - diff) / (2 * a)
			if root1 > 0 and root2 > 0:
				print(min(root1, root2))
			elif root1 > 0 and root2 < 0:
				print(root1)
			elif root1 < 0 and root2 > 0:
				print(root2)
		elif d == 0:
			root1 = b / (2 * a)
			print(root1)


from math import *
t = input()
t = int(t)
while t > 0:
	from sys import stdin, stdout
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = [int(x) for x in stdin.readline().rstrip().split()]
	x1 = cx - px
	y1 = cy - py
	z1 = cz - pz
	x2 = cx - qx
	y2 = cy - qy
	z2 = cz - qz
	x3 = qx - px
	y3 = qy - py
	z3 = qz - pz
	a = y1 * z2 - y2 * z1
	b = x2 * z1 - x1 * z2
	c = x1 * y2 - x2 * y1
	aa = z1 * dy - y1 * dz
	bb = x1 * dz - z1 * dx
	cc = y1 * dx - dy * x1
	c1 = aa * aa + bb * bb + cc * cc - r * r * dx * dx - r * r * dy * dy - r * r * dz * dz
	c2 = 2 * a * aa + 2 * b * bb + 2 * c * cc - 2 * r * r * x3 * dx - 2 * r * r * y3 * dy - 2 * r * r * z3 * dz
	c3 = a * a + b * b + c * c - r * r * x3 * x3 - r * r * y3 * y3 - r * r * z3 * z3
	if c1 == 0:
		ans = -1.0 * c3 / c2
	elif c2 == 0:
		ans = -1.0 * c3 / c1
		ans = sqrt(ans)
	else:
		dis = 1.0 * c2 * c2 - 4 * c1 * c3
		dis = sqrt(dis)
		ans1 = -1.0 * c2 + dis
		ans2 = -1.0 * c2 - dis
		ans1 = ans1 / (2 * c1)
		ans2 = ans2 / (2 * c1)
		if ans1 < ans2 and ans1 >= 0:
			ans = ans1
		elif ans2 < ans1 and ans2 >= 0:
			ans = ans2
		elif ans1 < ans2 and ans1 < 0:
			ans = ans2
		elif ans2 < ans1 and ans2 < 0:
			ans = ans1
		elif ans1 == ans2:
			ans = ans1
	print('{0:.16f}'.format(ans))
	t = t - 1


from math import sqrt
t = int(input())
for i in range(t):
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(int, input().split())
	c = cx ** 2 + cy ** 2 + cz ** 2 + px ** 2 + py ** 2 + pz ** 2 - 2 * (px * cx + py * cy + pz * cz) - r ** 2
	g1 = (px - cx) * (qx - px) + (py - cy) * (qy - py) + (pz - cz) * (qz - pz)
	g2 = (px - cx) * dx + (py - cy) * dy + (pz - cz) * dz
	g3 = (qx - px) ** 2 + (qy - py) ** 2 + (qz - pz) ** 2
	g4 = dx ** 2 + dy ** 2 + dz ** 2
	g5 = (qx - px) * dx + (qy - py) * dy + (qz - pz) * dz
	a1 = g2 ** 2 - c * g4
	b1 = 2 * g1 * g2 - 2 * c * g5
	c1 = g1 ** 2 - c * g3
	if a1 != 0:
		temp = sqrt(b1 ** 2 - 4 * a1 * c1)
		ans1 = (temp - b1) / (2 * a1)
		ans2 = (-temp - b1) / (2 * a1)
		if ans2 < 0:
			print(ans1)
		else:
			print(ans2)
	else:
		print(-c1 / b1)


from math import *
t = int(input().strip())
for i in range(t):
	(x1, y1, z1, x2, y2, z2, d1, d2, d3, xc, yc, zc, r) = [int(x) for x in input().strip().split(' ')]
	u = d2 * z1 - zc * d2 - y1 * d3 + yc * d3
	v = y2 * (z1 - zc) + y1 * (zc - z2) + yc * (z2 - z1)
	m = d1 * z1 - d1 * zc + xc * d3 - x1 * d3
	n = x2 * (z1 - zc) + x1 * (zc - z2) + xc * (z2 - z1)
	f = d1 * y1 - d1 * yc - d2 * x1 + d2 * xc
	g = x1 * (yc - y2) + x2 * (y1 - yc) + xc * (y2 - y1)
	X = x2 - x1
	Y = y2 - y1
	Z = z2 - z1
	C0 = u * u + m * m + f * f - r * r * (d1 * d1 + d2 * d2 + d3 * d3)
	C1 = 2 * (u * v + m * n + f * g - r * r * (X * d1 + Y * d2 + Z * d3))
	C2 = v * v + g * g + n * n - r * r * (X * X + Y * Y + Z * Z)
	if C0 == 0:
		print(-(C2 / C1))
	else:
		t1 = (-C1 + sqrt(C1 * C1 - 4 * C0 * C2)) / (2 * C0)
		t2 = (-C1 - sqrt(C1 * C1 - 4 * C0 * C2)) / (2 * C0)
		if t1 >= 0:
			print(t1 % 1000000000)
		else:
			print(t2 % 1000000000)


import math
P = [3, 0, 0]
Q = [-10, -10, 0]
D = [0, 10, 0]
C = [0, -3, 0]
r = 3.0

def cross(A, B):
	c = [A[1] * B[2] - B[1] * A[2], A[2] * B[0] - B[2] * A[0], A[0] * B[1] - B[0] * A[1]]
	return c

def dot(A, B):
	c = A[1] * B[1] + A[2] * B[2] + B[0] * A[0]
	return c

def diff(A, B):
	c = [A[0] - B[0], A[1] - B[1], A[2] - B[2]]
	return c

def scale(A, f):
	c = [f * A[0], f * A[1], f * A[2]]
	return c

def add(A, B):
	return [A[0] + B[0], A[1] + B[1], A[2] + B[2]]

def mod(A):
	return math.sqrt(A[0] * A[0] + A[1] * A[1] + A[2] * A[2])

def mod2(A):
	return A[0] * A[0] + A[1] * A[1] + A[2] * A[2]

def dist(A, fromB, fromC):
	ab = diff(A, fromB)
	ac = diff(A, fromC)
	bc = diff(fromB, fromC)
	nu = mod(cross(ab, ac))
	de = mod(bc)
	return nu / de

def dist(A, B):
	ab = diff(A, B)
	return mod(ab)

def mul(A, M):
	return [A[0] * M[0][0] + A[1] * M[1][0] + A[2] * M[2][0], A[0] * M[0][1] + A[1] * M[1][1] + A[2] * M[2][1], A[0] * M[0][2] + A[1] * M[1][2] + A[2] * M[2][2]]

def matmul(A, M):
	return [mul(A[0], M), mul(A[1], M), mul(A[2], M)]

def tr(M):
	return [[M[0][0], M[1][0], M[2][0]], [M[0][1], M[1][1], M[2][1]], [M[0][2], M[1][2], M[2][2]]]

def Res():
	global P, Q, D, C, r
	pc = diff(C, P)
	pq = diff(Q, P)
	p2 = mod2(pc)
	r2 = r * r
	delta = p2 - r2
	m = dot(pq, pc)
	n = dot(D, pc)
	k = mod2(pq)
	l = mod2(D)
	i = 2 * dot(pq, D)
	a = n * n - delta * l
	b = 2 * m * n - delta * i
	c = m * m - delta * k
	if a == 0:
		return -b / c
	d = b * b - 4 * a * c
	if d < 0:
		return 0
	d = math.sqrt(d)
	t1 = (-b + d) / (2 * a)
	t2 = (-b - d) / (2 * a)
	r1 = min(t1, t2)
	r2 = max(t1, t2)
	if r2 < 0:
		return 0
	if r1 < 0:
		return r2
	return r1

def Resxy():
	global P, Q, D, C, r
	PC = diff(C, P)
	pc = mod(PC)
	sn = r / pc
	cs = math.sqrt(1 - sn * sn)
	Rot = [[cs, -sn, 0], [sn, cs, 0], [0, 0, 1]]
	pro = mul(PC, Rot)
	PQ = diff(Q, P)
	t = (pro[1] * PQ[0] - pro[0] * PQ[1]) / (pro[0] * D[1] - D[0] * pro[1])
	Rot2 = [[cs, sn, 0], [-sn, cs, 0], [0, 0, 1]]
	pro2 = mul(PC, Rot2)
	t2 = (pro2[1] * PQ[0] - pro2[0] * PQ[1]) / (pro2[0] * D[1] - D[0] * pro2[1])
	r1 = min(t, t2)
	r2 = max(t, t2)
	if r2 < 0:
		return 0
	if r1 < 0:
		return r2
	return max(r1, 0)

def main():
	global P, Q, D, C, r
	t = int(input())
	while t > 0:
		L = [int(i) for i in input().split(' ')]
		P = [L[0], L[1], L[2]]
		Q = [L[3], L[4], L[5]]
		D = [L[6], L[7], L[8]]
		C = [L[9], L[10], L[11]]
		r = L[12]
		print(Res())
		t -= 1
main()


t = int(input())
while t:
	t -= 1
	(Px, Py, Pz, Qx, Qy, Qz, dx, dy, dz, cx, cy, cz, r) = [int(s) for s in input().split(' ')]
	ax = Px - cx
	x = Qx - Px
	ay = Py - cy
	y = Qy - Py
	az = Pz - cz
	z = Qz - Pz
	A = (az * dy - ay * dz) * (az * dy - ay * dz) + (az * dx - ax * dz) * (az * dx - ax * dz) + (ax * dy - ay * dx) * (ax * dy - ay * dx) - r * r * (dx * dx + dy * dy + dz * dz)
	C = (y * az - z * ay) * (y * az - z * ay) + (x * az - z * ax) * (x * az - z * ax) + (y * ax - x * ay) * (y * ax - x * ay) - r * r * (x * x + y * y + z * z)
	B = 2 * ((y * ax - x * ay) * (dy * ax - dx * ay) + (y * az - z * ay) * (dy * az - dz * ay) + (z * ax - x * az) * (dz * ax - dx * az) - r * r * (x * dx + y * dy + z * dz))
	if A == 0:
		time = -1 * C / B
	else:
		time = ((B * B - 4 * A * C) ** 0.5 - B) / (2 * A)
	print(time)


t = int(input())
while t:
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(int, input().split())
	a = px - cx
	b = py - cy
	c = pz - cz
	d = qx - cx
	e = qy - cy
	f = qz - cz
	alpha = a * d + b * e + c * f - r * r
	beta = a * dx + b * dy + c * dz
	k = a * a + b * b + c * c - r * r
	g = (dx * dx + dy * dy + dz * dz) * k
	h = (d * dx + e * dy + f * dz) * 2 * k
	i = (d * d + e * e + f * f - r * r) * k
	p = beta * beta - g
	q = 2 * alpha * beta - h
	r1 = alpha * alpha - i
	if p != 0:
		discr = (q * q - 4 * p * r1) ** (1 / 2)
		t1 = (-q + discr) / 2 / p
		t2 = (-q - discr) / 2 / p
		if t1 <= t2:
			if t1 >= 0:
				print(t1)
			else:
				print(t2)
		elif t2 >= 0:
			print(t2)
		else:
			print(t1)
	if p == 0:
		t1 = -r1 / q
		print(t1)
	t = t - 1


T = int(input())
for i1 in range(0, T):
	[Px, Py, Pz, Qx, Qy, Qz, dx, dy, dz, Cx, Cy, Cz, r] = [int(i) for i in input().split()]
	if (Pz == 0 and Qz == 0) and (dz == 0 and Cz == 0):
		a = Cx * Cx + Px * Px - r * r - 2 * Cx * Px
		b = 2 * (Cx * Py + Px * Cy - (Cx * Cy + Px * Py))
		c = Cy * Cy + Py * Py - 2 * Py * Cy - r * r
		x1 = Px - Qx
		y1 = Py - Qy
		a1 = a * dy * dy + b * dx * dy + c * dx * dx
		b1 = 2 * a * y1 * dy + y1 * dx * b + b * x1 * dy + 2 * c * x1 * dx
		c1 = a * y1 * y1 + b * y1 * x1 + c * x1 * x1
		if a1 == 0 and (c1 != 0 and b1 != 0):
			print(c1 / b1)
		elif b1 == 0:
			if c1 > 0 and a1 < 0 or (a1 > 0 and c1 < 0):
				k = c1 / a1
				print(k ** 0.5)
		else:
			dis = b1 ** 2 - 4 * a1 * c1
			if dis >= 0:
				dis = dis ** 0.5
				t1 = (b1 + dis) / (2 * a1)
				t2 = (b1 - dis) / (2 * a1)
				if t1 > 0 and t2 > 0:
					print(min(t1, t2))
				elif t1 > 0 and t2 < 0:
					print(t1)
				elif t1 < 0 and t2 > 0:
					print(t2)
	else:
		x1 = Qx - Cx
		y1 = Qy - Cy
		z1 = Qz - Cz
		AD2 = (Px - Cx) ** 2 + (Py - Cy) ** 2 + (Pz - Cz) ** 2 - r * r
		a = Px ** 2 + Py ** 2 + Pz ** 2 - Cx ** 2 - Cy ** 2 - Cz ** 2 + r ** 2 - AD2 - 2 * Px * Qx - 2 * Py * Qy - 2 * Pz * Qz + 2 * Cx * Qx + 2 * Cy * Qy + 2 * Cz * Qz
		b = 2 * Cx * dx + 2 * Cy * dy + 2 * Cz * dz - 2 * Py * dy - 2 * Px * dx - 2 * Pz * dz
		a1 = b ** 2 - 4 * AD2 * (dx ** 2 + dy ** 2 + dz ** 2)
		b1 = 2 * (-a * b + 4 * AD2 * (dx * (Qx - Cx) + dy * (Qy - Cy) + dz * (Qz - Cz)))
		k1 = x1 * x1 + y1 * y1 + z1 * z1
		k2 = 4 * AD2 * k1
		c1 = a ** 2 + 4 * AD2 * r * r - k2
		if a1 == 0 and (c1 != 0 and b1 != 0):
			print(c1 / b1)
		elif b1 == 0:
			k = c1 / a1
			print(k ** 0.5)
		else:
			dis = b1 ** 2 - 4 * a1 * c1
			if dis >= 0:
				dis = dis ** 0.5
				t1 = (b1 + dis) / (2 * a1)
				t2 = (b1 - dis) / (2 * a1)
				if t1 > 0 and t2 > 0:
					print(min(t1, t2))
				elif t1 > 0 and t2 < 0:
					print(t1)
				elif t1 < 0 and t2 > 0:
					print(t2)


t = int(input())
for c in range(t):
	(p, q, r, x, y, z, f, g, h, c, d, e, R) = input().split()
	p = int(p)
	q = int(q)
	r = int(r)
	x = int(x)
	y = int(y)
	z = int(z)
	f = int(f)
	g = int(g)
	h = int(h)
	c = int(c)
	d = int(d)
	e = int(e)
	R = int(R)
	a1 = e * y - d * z + d * r + q * z - r * y - e * q
	b1 = e * g - d * h + q * h - r * g
	a2 = c * z - e * x + e * p - p * z + r * x - c * r
	b2 = c * h - e * f - p * h + r * f
	a3 = c * q - p * d + p * y + d * x - q * x - c * y
	b3 = p * g + d * f - q * f - c * g
	lhc = R * R * ((x - p) * (x - p) + (y - q) * (y - q) + (z - r) * (z - r))
	lhs = R * R * (f * f + g * g + h * h)
	lhl = R * R * 2 * ((x - p) * f + (y - q) * g + (z - r) * h)
	rhc = a1 * a1 + a2 * a2 + a3 * a3
	rhs = b1 * b1 + b2 * b2 + b3 * b3
	rhl = 2 * (a1 * b1 + a2 * b2 + a3 * b3)
	fs = lhs - rhs
	fl = lhl - rhl
	fc = lhc - rhc
	if fs == 0:
		t1 = -1 * fc / fl
		print(t1)
	elif fl * fl - 4 * fs * fc == 0:
		t1 = -1 * fl / (2 * fs)
		print(t1)
	else:
		D = (fl * fl - 4 * fs * fc) ** 0.5
		t1 = (-1 * fl + D) / (2 * fs)
		t2 = (-1 * fl - D) / (2 * fs)
		if t1 > 0:
			print(t1)
		if t2 > 0:
			print(t2)


import math
t = int(input().strip(' '))
for __ in range(t):
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(int, input().split())
	r10 = qx - px
	r11 = qy - py
	r12 = qz - pz
	r00 = px - cx
	r02 = pz - cz
	r01 = py - cy
	res2 = r00 * r12 - r02 * r10
	res1 = r01 * r12 - r02 * r11
	res3 = r00 * r11 - r01 * r10
	ans3 = r00 * dy - r01 * dx
	ans1 = r01 * dz - r02 * dy
	ans2 = r00 * dz - r02 * dx
	A = ans1 ** 2 + ans2 ** 2 + ans3 ** 2 - r ** 2 * (dx ** 2 + dy ** 2 + dz ** 2)
	B = 2 * (res1 * ans1 + res2 * ans2 + res3 * ans3 - r ** 2 * (r10 * dx + r11 * dy + r12 * dz))
	C = res1 ** 2 + res2 ** 2 + res3 ** 2 - r ** 2 * (r10 ** 2 + r11 ** 2 + r12 ** 2)
	D = B ** 2 - 4 * A * C
	if A < 0:
		A *= -1
		B *= -1
		C *= -1
	ANS = 0
	if A == 0:
		ANS = -1 * (C / B)
	else:
		d = math.sqrt(D)
		ANS = max(-B + d, -B - d)
		ANS = ANS / (2 * A)
	print('%.10f' % ANS)


from math import *
T = int(input())
for t in range(0, T):
	o = input().split()
	p1 = int(o[0])
	p2 = int(o[1])
	p3 = int(o[2])
	q1 = int(o[3])
	q2 = int(o[4])
	q3 = int(o[5])
	d1 = int(o[6])
	d2 = int(o[7])
	d3 = int(o[8])
	c1 = int(o[9])
	c2 = int(o[10])
	c3 = int(o[11])
	r = int(o[12])
	a1 = p1 - c1
	a2 = p2 - c2
	a3 = p3 - c3
	b1 = p1 - q1
	b2 = p2 - q2
	b3 = p3 - q3
	z = r * r
	l1 = a1 * b2 - a2 * b1
	l2 = a2 * b3 - a3 * b2
	l3 = a1 * b3 - a3 * b1
	k1 = a2 * d1 - a1 * d2
	k2 = a3 * d2 - a2 * d3
	k3 = a3 * d1 - a1 * d3
	A = z * (d1 * d1 + d2 * d2 + d3 * d3) - (k1 * k1 + k2 * k2 + k3 * k3)
	B = 2 * (z * (b1 * d1 + b2 * d2 + b3 * d3) + l1 * k1 + l2 * k2 + l3 * k3)
	C = z * (b1 * b1 + b2 * b2 + b3 * b3) - l1 * l1 - l2 * l2 - l3 * l3
	if A == 0:
		print(B / C)
	else:
		D = sqrt(B * B - 4 * A * C)
		ans1 = (B + D) / (2 * A)
		ans2 = (B - D) / (2 * A)
		if ans1 >= 0:
			print(ans1)
		elif ans2 >= 0:
			print(ans2)


import math
T = int(input())
for t in range(T):
	(Px, Py, Pz, Qx, Qy, Qz, dx, dy, dz, Cx, Cy, Cz, r) = map(int, input().split())
	a = Px - Cx
	b = Py - Cy
	f = Pz - Cz
	m = Qx - Px
	n = Qy - Py
	s = Qz - Pz
	Z = a * a + b * b + f * f - r * r
	k = a * dx + b * dy + f * dz
	u = a * m + b * n + f * s
	D = dx * dx + dy * dy + dz * dz
	v = 2 * m * dx + 2 * n * dy + 2 * s * dz
	q = m * m + n * n + s * s
	A = k * k - D * Z
	B = 2 * k * u - v * Z
	C = u * u - q * Z
	if A == 0:
		t = -C / B
		print(t)
	else:
		t1 = (-B + math.sqrt(B * B - 4 * A * C)) / (2 * A)
		t2 = (-B - math.sqrt(B * B - 4 * A * C)) / (2 * A)
		if t1 < 0:
			print(t2)
		elif t2 < 0:
			print(t1)
		elif t1 <= t2:
			print(t1)
		else:
			print(t2)


import math
test = int(input())
while test:
	(qx, qy, qz, px, py, pz, dx, dy, dz, sx, sy, sz, r) = input().split()
	qx = float(qx)
	qy = float(qy)
	qz = float(qz)
	px = float(px)
	py = float(py)
	pz = float(pz)
	dx = float(dx)
	dy = float(dy)
	dz = float(dz)
	sx = float(sx)
	sy = float(sy)
	sz = float(sz)
	r = float(r)
	constntVelocity = float(math.sqrt(dx * dx + dy * dy + dz * dz))
	px = px - sx
	py -= sy
	pz -= sz
	qx = qx - sx
	qy -= sy
	qz -= sz
	px1 = px
	py1 = py
	pz1 = pz
	sx = 0
	sy = 0
	sz = 0
	C = qx * qx + qy * qy + qz * qz - r * r
	cn1 = dx * dx + dy * dy + dz * dz
	cn2 = 2 * dx * px - 2 * dx * qx + 2 * dy * (py - qy) + 2 * dz * (pz - qz)
	cn3 = px * px + py * py + pz * pz + (qx * qx + qy * qy + qz * qz) - 2 * (qx * px + qy * py + qz * pz)
	pn1 = 2 * (dx * qx + dy * qy + dz * qz)
	pn2 = 2 * (qx * (px - qx) + qy * (py - qy) + qz * (pz - qz))
	a = pn1 * pn1 - 4 * C * cn1
	b = 2 * pn1 * pn2 - 4 * C * cn2
	c = pn2 * pn2 - 4 * C * cn3
	distpp_upd = 0
	TimeofVision = 0
	if a == 0.0:
		k = -c / b
		px = dx * k + px
		py = dy * k + py
		pz = dz * k + pz
		distpp_upd = float(math.sqrt((px1 - px) * (px1 - px) + (py1 - py) * (py1 - py) + (pz1 - pz) * (pz1 - pz)))
		TimeofVision = float(distpp_upd / constntVelocity)
		print(TimeofVision)
		test = test - 1
		continue
	k1 = float((-b + math.sqrt(b * b - 4 * a * c)) / (2 * a))
	k2 = float((-b - math.sqrt(b * b - 4 * a * c)) / (2 * a))
	if abs(k1 - k2) == 0:
		px = dx * k1 + px
		py = dy * k1 + py
		pz = dz * k1 + pz
	else:
		g1 = dx * k1 + px1
		g2 = dy * k1 + py1
		g3 = dz * k1 + pz1
		g1 = g1 - px1
		g2 = g2 - py1
		g3 = g3 - pz1
		jnp = float(math.sqrt(g1 * g1 + g2 * g2 + g3 * g3))
		u1 = g1 / jnp
		u2 = g2 / jnp
		u3 = g3 / jnp
		ud1 = float(dx / constntVelocity)
		ud2 = float(dy / constntVelocity)
		ud3 = float(dy / constntVelocity)
		if abs(ud1 - u1) == 0.0 and abs(ud2 - u2) == 0.0 and (abs(ud3 - u3) == 0.0):
			px = dx * k1 + px1
			py = dy * k1 + py1
			pz = dz * k1 + pz1
		else:
			px = dx * k2 + px1
			py = dy * k2 + py1
			pz = dz * k2 + pz1
	distpp_upd = float(math.sqrt((px1 - px) * (px1 - px) + (py1 - py) * (py1 - py) + (pz1 - pz) * (pz1 - pz)))
	TimeofVision = float(distpp_upd / constntVelocity)
	print(TimeofVision)
	test = test - 1


import math

def dot(l1, l2):
	return l1[0] * l2[0] + l1[1] * l2[1] + l1[2] * l2[2]

def mod(l):
	return l[0] ** 2 + l[1] ** 2 + l[2] ** 2

def sub(l1, l2):
	return [l1[0] - l2[0], l1[1] - l2[1], l1[2] - l2[2]]
a = int(input())
for _ in range(a):
	(b1, b2, b3, c1, c2, c3, d1, d2, d3, e1, e2, e3, r) = [int(j) for j in input().split()]
	P = [b1, b2, b3]
	Q = [c1, c2, c3]
	d = [d1, d2, d3]
	C = [e1, e2, e3]
	f1 = (mod(sub(P, C)) - r ** 2) * mod(d) - dot(d, sub(P, C)) ** 2
	f2 = -2 * dot(sub(P, Q), d) * (mod(sub(P, C)) - r ** 2) + 2 * dot(sub(P, Q), sub(P, C)) * dot(d, sub(P, C))
	f3 = mod(sub(P, Q)) * (mod(sub(P, C)) - r ** 2) - dot(sub(P, Q), sub(P, C)) ** 2
	if f1 == 0:
		print(-f3 / f2)
	else:
		aw = (-f2 + math.sqrt(f2 ** 2 - 4 * f1 * f3)) / (2 * f1)
		sw = (-f2 - math.sqrt(f2 ** 2 - 4 * f1 * f3)) / (2 * f1)
		if aw > 0 and sw > 0:
			print(min([aw, sw]))
		else:
			print(max([aw, sw]))


from math import sqrt

def sqr(a):
	return a * a
for _ in range(int(input())):
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(int, input().split())
	g = qx - px
	h = qy - py
	i = qz - pz
	d = px - cx
	e = py - cy
	f = pz - cz
	m = dx
	n = dy
	o = dz
	var1 = sqr(px - cx) + sqr(py - cy) + sqr(pz - cz) - sqr(r)
	a = sqr(m) * (sqr(d) - var1) + sqr(n) * (sqr(e) - var1) + sqr(o) * (sqr(f) - var1) + 2 * d * e * m * n + 2 * e * f * n * o + 2 * d * f * m * o
	b = 2 * g * m * (sqr(d) - var1) + 2 * h * n * (sqr(e) - var1) + 2 * i * o * (sqr(f) - var1) + 2 * d * e * (g * n + h * m) + 2 * e * f * (h * o + i * n) + 2 * d * f * (g * o + m * i)
	c = sqr(g) * (sqr(d) - var1) + sqr(h) * (sqr(e) - var1) + sqr(i) * (sqr(f) - var1) + 2 * d * e * g * h + 2 * e * f * h * i + 2 * d * f * g * i
	(ans, ans1, ans2) = (0, 0, 0)
	if a != 0:
		ans1 = (-b + sqrt(sqr(b) - 4 * a * c)) / (2 * a)
		ans2 = (-b - sqrt(sqr(b) - 4 * a * c)) / (2 * a)
		if ans1 > 0 and ans2 > 0:
			ans = min(ans1, ans2)
		else:
			ans = max(ans1, ans2)
	else:
		ans = -(b / c)
	print(float(ans))


import math
T = int(input())
for t in range(T):
	(Px, Py, Pz, Qx, Qy, Qz, dx, dy, dz, xo, yo, zo, r) = list(map(float, input().strip().split(' ')))
	(kpox, kpoy, kpoz) = (Px - xo, Py - yo, Pz - zo)
	(kpqx, kpqy, kpqz) = (Px - Qx, Py - Qy, Pz - Qz)
	c = kpox ** 2 + kpoy ** 2 + kpoz ** 2 - r ** 2
	b2deg = dx * kpox + dy * kpoy + dz * kpoz
	bconst = kpox * kpqx + kpoy * kpqy + kpoz * kpqz
	a2deg = dx ** 2 + dy ** 2 + dz ** 2
	a1deg = -2 * (kpqx * dx + kpqy * dy + kpqz * dz)
	aconst = kpqx ** 2 + kpqy ** 2 + kpqz ** 2
	finala = b2deg ** 2 - c * a2deg
	finalb = -(2 * bconst * b2deg) - c * a1deg
	finalc = bconst ** 2 - c * aconst
	if finala != 0:
		ans = (-finalb - (finalb ** 2 - 4 * finala * finalc) ** (1 / 2)) / (2 * finala)
	else:
		ans = -finalc / finalb
	print(ans)


import math

def ret_N_R(px, py, pz, qx, qy, qz, vx, vy, vz, ox, oy, oz):
	Nx = oy * qz - oz * qy + oz * py - oy * pz
	Ny = oz * qx - ox * qz + ox * pz - oz * px
	Nz = ox * qy - oy * qx + oy * px - ox * py
	Rx = oy * vz - oz * vy
	Ry = oz * vx - ox * vz
	Rz = ox * vy - oy * vx
	return (Nx, Ny, Nz, Rx, Ry, Rz)

def quad_coeff(px, py, pz, qx, qy, qz, vx, vy, vz, cx, cy, cz, r):
	ox = px - cx
	oy = py - cy
	oz = pz - cz
	Dx = qx - px
	Dy = qy - py
	Dz = qz - pz
	(Nx, Ny, Nz, Rx, Ry, Rz) = ret_N_R(px, py, pz, qx, qy, qz, vx, vy, vz, ox, oy, oz)
	a = r * r * (vx * vx + vy * vy + vz * vz) - (Rx * Rx + Ry * Ry + Rz * Rz)
	b = 2 * (r * r * (Dx * vx + Dy * vy + Dz * vz) - (Nx * Rx + Ny * Ry + Nz * Rz))
	c = r * r * (Dx * Dx + Dy * Dy + Dz * Dz) - (Nx * Nx + Ny * Ny + Nz * Nz)
	return (a, b, c)

def pos_root(a, b, c):
	det = math.sqrt(b * b - 4 * a * c)
	if a == 0:
		soln = 1
	else:
		s1 = (-1 * b - det) / (2 * a)
		s2 = (det - b) / (2 * a)
		if s1 >= 0:
			soln = s1
		elif s2 >= 0:
			soln = s2
		else:
			soln = 0
	return soln
T = int(input())
for i in range(0, T):
	(Px, Py, Pz, Qx, Qy, Qz, Vx, Vy, Vz, Cx, Cy, Cz, r) = map(float, input().split())
	(a, b, c) = quad_coeff(Px, Py, Pz, Qx, Qy, Qz, Vx, Vy, Vz, Cx, Cy, Cz, r)
	tm = pos_root(a, b, c)
	print(tm)


import math
t = int(input().strip())
for _ in range(t):
	(p0, p1, p2, q0, q1, q2, d0, d1, d2, c0, c1, c2, r) = [int(x) for x in input().strip().split(' ')]
	pc0 = p0 - c0
	pc1 = p1 - c1
	pc2 = p2 - c2
	sqt1 = pc1 * d2 - pc2 * d1
	sqt2 = pc0 * d1 - pc1 * d0
	sqt3 = pc2 * d0 - pc0 * d2
	lt1 = q1 * c2 - q2 * c1 + p2 * c1 - p1 * c2 + p1 * q2 - p2 * q1
	lt2 = q0 * c1 - q1 * c0 + p1 * c0 - p0 * c1 + p0 * q1 - p1 * q0
	lt3 = q2 * c0 - q0 * c2 + p0 * c2 - p2 * c0 + p2 * q0 - p0 * q2
	s1 = d0 * r
	s2 = d1 * r
	s3 = d2 * r
	l1 = q0 * r - p0 * r
	l2 = q1 * r - p1 * r
	l3 = q2 * r - p2 * r
	a = s1 ** 2 + s2 ** 2 + s3 ** 2 - sqt1 ** 2 - sqt2 ** 2 - sqt3 ** 2
	b = 2 * (s1 * l1 + s2 * l2 + s3 * l3 - sqt1 * lt1 - sqt2 * lt2 - sqt3 * lt3)
	c = l1 ** 2 + l2 ** 2 + l3 ** 2 - lt1 ** 2 - lt2 ** 2 - lt3 ** 2
	if a == 0:
		t = -1 * c / b
		print(t)
	else:
		srt = math.sqrt(b ** 2 - 4 * a * c)
		sol1 = -1 * b + srt
		sol2 = -1 * b - srt
		sol1 /= 2 * a
		sol2 /= 2 * a
		sol = min(sol1, sol2)
		if sol < 0:
			print(max(sol1, sol2))
		else:
			print(sol)


class point:

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

def sub(p, q):
	return point(p.x - q.x, p.y - q.y, p.z - q.z)

def dot(p, q):
	return p.x * q.x + p.y * q.y + p.z * q.z

def cross(p, q):
	return point(p.y * q.z - p.z * q.y, p.z * q.x - p.x * q.z, p.x * q.y - p.y * q.x)

def modsq(p):
	return p.x ** 2 + p.y ** 2 + p.z ** 2

def solve():
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(int, input().split())
	p = point(px, py, pz)
	q = point(qx, qy, qz)
	d = point(dx, dy, dz)
	c = point(cx, cy, cz)
	c1 = modsq(cross(d, sub(c, p))) - modsq(d) * r * r
	c2 = dot(cross(sub(q, p), sub(c, p)), cross(d, sub(c, p))) - r * r * dot(d, sub(q, p))
	c2 *= 2
	c3 = modsq(cross(sub(q, p), sub(c, p))) - modsq(sub(q, p)) * r * r
	if c1 == 0:
		print(-c3 / c2)
		return
	print((-c2 + (c2 ** 2 - 4 * c1 * c3) ** 0.5) / (2 * c1))
t = int(input())
for i in range(t):
	solve()


import math

def square(f):
	return f * f

def dist(px, py, pz, cx, cy, cz):
	a1 = square(px - cx)
	b1 = square(py - cy)
	c1 = square(pz - cz)
	return a1 + b1 + c1
t = int(input())
for i in range(t):
	inp = input().split()
	px = int(inp[0])
	py = int(inp[1])
	pz = int(inp[2])
	qx = int(inp[3])
	qy = int(inp[4])
	qz = int(inp[5])
	dx = int(inp[6])
	dy = int(inp[7])
	dz = int(inp[8])
	cx = int(inp[9])
	cy = int(inp[10])
	cz = int(inp[11])
	r = int(inp[12])
	a = qx - px
	b = qy - py
	c = qz - pz
	d = square(a) + square(b) + square(c)
	e = square(dx) + square(dy) + square(dz)
	f = 2 * a * dx + 2 * b * dy + 2 * c * dz
	g = qx - cx
	h = qy - cy
	i1 = qz - cz
	i = square(g) + square(h) + square(i1)
	j = 2 * g * dx + 2 * h * dy + 2 * i1 * dz
	k = dist(px, py, pz, cx, cy, cz) - square(r)
	l = i - square(r) - d + k
	m = j - f
	n = 4 * k * e - square(m)
	o = 4 * k * j - 2 * l * m
	p = 4 * k * (i - square(r)) - square(l)
	if n == 0:
		print(-p / o)
	else:
		alpha = (-o + math.sqrt(square(o) - 4 * n * p)) / (2 * n)
		beta = (-o - math.sqrt(square(o) - 4 * n * p)) / (2 * n)
		if alpha > 0 and beta > 0:
			print(min(alpha, beta))
		elif alpha < 0 and beta > 0:
			print(beta)
		elif alpha > 0 and beta < 0:
			print(alpha)
		elif alpha < 0 and beta < 0:
			print(-1)


from math import sqrt
for i in range(int(input())):
	(px, py, pz, qx, qy, qz, dx, dy, dz, cx, cy, cz, r) = map(int, input().split())
	a = (qx - px) * (cx - px) + (qy - py) * (cy - py) + (qz - pz) * (cz - pz)
	b = dx * (cx - px) + dy * (cy - py) + dz * (cz - pz)
	c = (cx - px) * (cx - px) + (cy - py) * (cy - py) + (cz - pz) * (cz - pz) - r * r
	d = dx * dx + dy * dy + dz * dz
	e = (qx - px) * (qx - px) + (qy - py) * (qy - py) + (qz - pz) * (qz - pz)
	f = 2 * (dx * (qx - px) + dy * (qy - py) + dz * (qz - pz))
	A = b * b - c * d
	B = 2 * a * b - c * f
	C = a * a - c * e
	p = sqrt(B * B - 4 * A * C)
	if A == 0:
		ans = -1 * (C / B)
		print('{0:.10f}'.format(ans))
	else:
		ans = (p - B) / (2 * A)
		ans1 = -1 * ((p + B) / (2 * A))
		if ans > 0 and ans1 > 0:
			print('{0:.10f}'.format(min(ans, ans1)))
		elif ans > 0 and ans1 < 0:
			print('{0:.10f}'.format(ans))
		elif ans < 0 and ans1 > 0:
			print('{0:.10f}'.format(ans1))


def dot(ax, ay, az, bx, by, bz):
	return ax * bx + ay * by + az * bz

def findRoot(a, b, c):
	R1 = (-b + (b * b - 4 * a * c) ** 0.5) / (2 * a)
	R2 = (-b - (b * b - 4 * a * c) ** 0.5) / (2 * a)
	return (R1, R2)
T = int(input())
while T > 0:
	T -= 1
	points = input().split()
	for i in range(len(points)):
		points[i] = float(points[i])
	px = points[0]
	py = points[1]
	pz = points[2]
	qx = points[3]
	qy = points[4]
	qz = points[5]
	dx = points[6]
	dy = points[7]
	dz = points[8]
	cx = points[9]
	cy = points[10]
	cz = points[11]
	r = points[12]
	QPX = qx - px
	QPY = qy - py
	QPZ = qz - pz
	CPX = cx - px
	CPY = cy - py
	CPZ = cz - pz
	c1 = dot(QPX, QPY, QPZ, QPX, QPY, QPZ)
	c2 = 2 * dot(QPX, QPY, QPZ, dx, dy, dz)
	c3 = dot(dx, dy, dz, dx, dy, dz)
	lol = dot(QPX, QPY, QPZ, CPX, CPY, CPZ)
	lawl = dot(dx, dy, dz, CPX, CPY, CPZ)
	lmao = dot(CPX, CPY, CPZ, CPX, CPY, CPZ)
	a = r ** 2 * c3 - lmao * c3 + lawl ** 2
	b = r ** 2 * c2 - lmao * c2 + 2 * lol * lawl
	c = r ** 2 * c1 - lmao * c1 + lol ** 2
	if a == 0:
		print(-c / b)
		continue
	(t1, t2) = findRoot(a, b, c)
	if t1 < 0:
		print(t2)
	elif t2 < 0:
		print(t1)
	else:
		print(min(t1, t2))


import math
N = int(input())
for i in range(N):
	op = input().split(' ')
	Px = int(op[0])
	Py = int(op[1])
	Pz = int(op[2])
	Qx = int(op[3])
	Qy = int(op[4])
	Qz = int(op[5])
	Dx = int(op[6])
	Dy = int(op[7])
	Dz = int(op[8])
	Cx = int(op[9])
	Cy = int(op[10])
	Cz = int(op[11])
	R = int(op[12])
	C = Cx * Cx + Cy * Cy + Cz * Cz + Px * Px + Py * Py + Pz * Pz - 2 * (Px * Cx + Py * Cy + Pz * Cz) - R * R
	Kx = Cx - Px
	Ky = Cy - Py
	Kz = Cz - Pz
	lambdaX = Qx - Px
	lambdaY = Qy - Py
	lambdaZ = Qz - Pz
	a = (Kx * Kx - C) * (Dx * Dx) + (Ky * Ky - C) * (Dy * Dy) + (Kz * Kz - C) * (Dz * Dz) + 2 * (Kx * Ky * Dx * Dy + Kx * Kz * Dx * Dz + Ky * Kz * Dy * Dz)
	b = (Kx * Kx - C) * (2 * lambdaX * Dx) + (Ky * Ky - C) * (2 * lambdaY * Dy) + (Kz * Kz - C) * (2 * lambdaZ * Dz) + (2 * Kx * Ky * (lambdaY * Dx + lambdaX * Dy) + 2 * Ky * Kz * (lambdaZ * Dy + lambdaY * Dz) + 2 * Kx * Kz * (lambdaX * Dz + lambdaZ * Dx))
	c = (Kx * Kx - C) * (lambdaX * lambdaX) + (Ky * Ky - C) * (lambdaY * lambdaY) + (Kz * Kz - C) * (lambdaZ * lambdaZ) + 2 * Kx * Ky * lambdaX * lambdaY + 2 * Kx * Kz * lambdaX * lambdaZ + 2 * Ky * Kz * lambdaY * lambdaZ
	A = (Kz * Dy - Ky * Dz) * (Kz * Dy - Ky * Dz) + (Kz * Dx - Kx * Dz) * (Kz * Dx - Kx * Dz) + (Ky * Dx - Kx * Dy) * (Ky * Dx - Kx * Dy) - R * R * (Dx * Dx + Dy * Dy + Dz * Dz)
	B = 2 * ((Kz * lambdaY - Ky * lambdaZ) * (Kz * Dy - Ky * Dz) + (Kz * lambdaX - Kx * lambdaZ) * (Kz * Dx - Kx * Dz) + (Ky * lambdaX - Kx * lambdaY) * (Ky * Dx - Kx * Dy)) - 2 * R * R * (lambdaX * Dx + lambdaY * Dy + lambdaZ * Dz)
	C = (Kz * lambdaY - Ky * lambdaZ) * (Kz * lambdaY - Ky * lambdaZ) + (Kz * lambdaX - Kx * lambdaZ) * (Kz * lambdaX - Kx * lambdaZ) + (Ky * lambdaX - Kx * lambdaY) * (Ky * lambdaX - Kx * lambdaY) - R * R * (lambdaX * lambdaX + lambdaY * lambdaY + lambdaZ * lambdaZ)
	d = B * B - 4 * A * C
	sqrt_val = math.sqrt(abs(d))
	if A == 0:
		print(-C / B)
	else:
		r1 = (-B + sqrt_val) / (2 * A)
		r2 = (-B - sqrt_val) / (2 * A)
		if r2 < 0 and r1 >= 0:
			print(r1)
		elif r2 < 0 and r1 < 0:
			print(min(abs(r1), abs(r2)))
		else:
			print(min(abs(r2), abs(r1)))


import math
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	(p1, p2, p3) = (l[0], l[1], l[2])
	(q1, q2, q3) = (l[3], l[4], l[5])
	(d1, d2, d3) = (l[6], l[7], l[8])
	(c1, c2, c3, r) = (l[9], l[10], l[11], l[12])
	lam1 = (q1 - p1) ** 2 + (q2 - p2) ** 2 + (q3 - p3) ** 2
	lam2 = d1 ** 2 + d2 ** 2 + d3 ** 2
	lam3 = 2 * ((q1 - p1) * d1 + (q2 - p2) * d2 + (q3 - p3) * d3)
	nu1 = (q1 - c1) ** 2 + (q2 - c2) ** 2 + (q3 - c3) ** 2
	nu2 = 2 * ((q1 - c1) * d1 + (q2 - c2) * d2 + (q3 - c3) * d3)
	cons = math.sqrt((p1 - c1) ** 2 + (p2 - c2) ** 2 + (p3 - c3) ** 2 - r ** 2)
	alph = -1 * (lam1 - nu1 + r ** 2 - cons ** 2)
	bet = -1 * (lam3 - nu2)
	A = -1 * (bet ** 2 - 4 * cons ** 2 * lam2)
	B = -1 * (2 * alph * bet - 4 * cons ** 2 * nu2)
	C = -1 * (alph ** 2 - 4 * cons ** 2 * nu1 + 4 * cons ** 2 * r ** 2)
	if A == 0:
		t = -B / C
		print(t)
		break
	D = math.sqrt(B ** 2 - 4 * A * C)
	t1 = (-1 * B - D) / (2 * A)
	t2 = (-1 * B + D) / (2 * A)
	if t1 > 0 and t2 < 0:
		print(t1)
	elif t1 < 0 and t2 > 0:
		print(t2)
	else:
		print(min(t1, t2))


def StringListToNumList(L):
	for i in range(0, len(L), 1):
		L[i] = int(L[i])
	return L

def DotProduct(Ax, Ay, Az, Bx, By, Bz):
	Answer = Ax * Bx + Ay * By + Az * Bz
	return Answer
T = int(input(''))
for k in range(0, T, 1):
	Input = input('')
	Input = Input.split(' ')
	Px = int(Input[0])
	Py = int(Input[1])
	Pz = int(Input[2])
	Qx = int(Input[3])
	Qy = int(Input[4])
	Qz = int(Input[5])
	dx = int(Input[6])
	dy = int(Input[7])
	dz = int(Input[8])
	cx = int(Input[9])
	cy = int(Input[10])
	cz = int(Input[11])
	r = int(Input[12])
	Ax = Qx - Px
	Ay = Qy - Py
	Az = Qz - Pz
	Axy = Ax * Ay
	Ayz = Ay * Az
	Azx = Az * Ax
	Kx = Px - cx
	Ky = Py - cy
	Kz = Pz - cz
	Kxy = Kx * Ky
	Kyz = Ky * Kz
	Kzx = Kz * Kx
	A1 = Ky ** 2 + Kz ** 2 - r ** 2
	A2 = Kx ** 2 + Kz ** 2 - r ** 2
	A3 = Kx ** 2 + Ky ** 2 - r ** 2
	dxy = dx * dy
	dyz = dy * dz
	dzx = dz * dx
	AA = A1 * dx ** 2 + A2 * dy ** 2 + A3 * dz ** 2
	BB = Ax * A1 * dx + Ay * A2 * dy + Az * A3 * dz
	CC = A1 * Ax ** 2 + A2 * Ay ** 2 + A3 * Az ** 2
	X = 2 * DotProduct(Kxy, Kyz, Kzx, dxy, dyz, dzx) - AA
	Y = 2 * (Kxy * (Ax * dy + Ay * dx) + Kyz * (Ay * dz + Az * dy) + Kzx * (Az * dx + Ax * dz) - BB)
	Z = 2 * DotProduct(Kxy, Kyz, Kzx, Axy, Ayz, Azx) - CC
	if X == 0:
		print(Z * -1 / Y)
	else:
		Answer1 = (-1 * Y + (Y ** 2 - 4 * X * Z) ** 0.5) / (2 * X)
		if Answer1 >= 0:
			print(Answer1)
		else:
			Answer2 = (-1 * Y - (Y ** 2 - 4 * X * Z) ** 0.5) / (2 * X)
			print(Answer2)


x = int(input())
for i in range(x):
	arr = list(map(int, input().split()))
	px = arr[0]
	py = arr[1]
	pz = arr[2]
	qx = arr[3] - arr[0]
	qy = arr[4] - arr[1]
	qz = arr[5] - arr[2]
	dx = arr[6]
	dy = arr[7]
	dz = arr[8]
	cx = arr[9]
	cy = arr[10]
	cz = arr[11]
	r = arr[12]
	x_ = r ** 2 + (px - cx) ** 2 - ((px - cx) * (px - cx) + (py - cy) * (py - cy) + (pz - cz) * (pz - cz))
	y_ = r ** 2 + (py - cy) ** 2 - ((px - cx) * (px - cx) + (py - cy) * (py - cy) + (pz - cz) * (pz - cz))
	z_ = r ** 2 + (pz - cz) ** 2 - ((px - cx) * (px - cx) + (py - cy) * (py - cy) + (pz - cz) * (pz - cz))
	a1 = x_ * dx * dx + y_ * dy * dy + z_ * dz * dz
	a2 = 2 * ((px - cx) * (py - cy) * dx * dy + (pz - cz) * (py - cy) * dz * dy + (px - cx) * (pz - cz) * dx * dz)
	B = 2 * (x_ * qx * dx + y_ * qy * dy + z_ * qz * dz + (px - cx) * (py - cy) * qx * dy + (px - cx) * (py - cy) * qy * dx + (px - cx) * (pz - cz) * qx * dz + (px - cx) * (pz - cz) * qz * dx + (pz - cz) * (py - cy) * qz * dy + (pz - cz) * (py - cy) * qy * dz)
	c1 = x_ * qx * qx + y_ * qy * qy + z_ * qz * qz
	c2 = 2 * (px - cx) * (py - cy) * qx * qy + 2 * (px - cx) * (pz - cz) * qx * qz + 2 * (pz - cz) * (py - cy) * qz * qy
	if a1 + a2 == 0:
		print(-(c1 + c2) / B)
	else:
		ans1 = (-B + (B ** 2 - 4 * (a1 + a2) * (c1 + c2)) ** 0.5) / (2 * (a1 + a2))
		ans2 = (-B - (B ** 2 - 4 * (a1 + a2) * (c1 + c2)) ** 0.5) / (2 * (a1 + a2))
		if ans1 >= 0 and ans2 >= 0:
			if ans1 > ans2:
				print(ans1)
			else:
				print(ans2)
		elif ans2 >= 0:
			print(ans2)
		else:
			print(ans1)


t = int(input())
for i in range(t):
	lis = input()
	arr = list(map(int, lis.split(' ')))
	x1 = arr[0]
	y1 = arr[1]
	z1 = arr[2]
	x0 = arr[3]
	y0 = arr[4]
	z0 = arr[5]
	d1 = arr[6]
	d2 = arr[7]
	d3 = arr[8]
	x3 = arr[9]
	y3 = arr[10]
	z3 = arr[11]
	r = arr[12]
	k = (x0 - x1) * (x1 - x3) + (y0 - y1) * (y1 - y3) + (z0 - z1) * (z1 - z3)
	k1 = d1 * (x1 - x3) + d2 * (y1 - y3) + d3 * (z1 - z3)
	k2 = x3 * x3 + y3 * y3 + z3 * z3 + x1 * x1 + y1 * y1 + z1 * z1 - 2 * (x1 * x3 + y1 * y3 + z1 * z3) - r * r
	k3 = (x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1) + (z0 - z1) * (z0 - z1)
	k4 = d1 * d1 + d2 * d2 + d3 * d3
	k5 = d1 * (x0 - x1) + d2 * (y0 - y1) + d3 * (z0 - z1)
	a = k1 * k1 - k2 * k4
	b = 2 * (k * k1 - k2 * k5)
	c = k * k - k2 * k3
	if a != 0:
		t1 = float((-b + (b * b - 4 * a * c) ** 0.5) / (2 * a))
		t2 = float((-b - (b * b - 4 * a * c) ** 0.5) / (2 * a))
		if t1 > 0 and t2 > 0:
			ans = float(min(t1, t2))
			print('%.9f' % ans)
		elif t1 > 0:
			print('%.9f' % t1)
		else:
			print('%.9f' % t2)
	else:
		t = float(-c / b)
		print('%.9f' % t)


import math
T = int(input().strip())
if T >= 1 and T <= 10 ** 5:
	for eachTestCase in range(T):
		par = [int(i) for i in input().strip().split()]
		(px, py, pz) = (par[0], par[1], par[2])
		(qx, qy, qz) = (par[3], par[4], par[5])
		(dx, dy, dz) = (par[6], par[7], par[8])
		(cx, cy, cz, r) = (par[9], par[10], par[11], par[12])
		if r > 0 and r <= 10 ** 9 and (abs(px) <= 2 * 10 ** 9) and (abs(py) <= 2 * 10 ** 9) and (abs(pz) <= 2 * 10 ** 9) and (abs(qx) <= 2 * 10 ** 9) and (abs(qy) <= 2 * 10 ** 9) and (abs(qz) <= 2 * 10 ** 9) and (abs(dx) <= 2 * 10 ** 9) and (abs(dy) <= 2 * 10 ** 9) and (abs(dz) <= 2 * 10 ** 9) and (abs(cx) <= 2 * 10 ** 9) and (abs(cy) <= 2 * 10 ** 9) and (abs(cz) <= 2 * 10 ** 9):
			(pqx, pqy, pqz, pcx, pcy, pcz) = (px - qx, py - qy, pz - qz, px - cx, py - cy, pz - cz)
			(a2qu, a2rem, a2val) = (dx ** 2 + dy ** 2 + dz ** 2, pqx ** 2 + pqy ** 2 + pqz ** 2, 2 * (dx * pqx + dy * pqy + dz * pqz))
			(b2rem, b2val) = (2 * (pqx * pcx + pqy * pcy + pqz * pcz), 2 * (dx * pcx + dy * pcy + dz * pcz))
			c = pcx ** 2 + pcy ** 2 + pcz ** 2 - r ** 2
			(tqu, tval, trem) = (b2val ** 2 - 4 * c * a2qu, 4 * c * a2val - 2 * b2rem * b2val, b2rem ** 2 - 4 * c * a2rem)
			if tqu == 0:
				print(trem * -1 / tval)
			else:
				detval = tval ** 2 - 4 * tqu * trem
				if detval >= 0:
					root1 = (tval * -1 + math.sqrt(detval)) / (2 * tqu)
					root2 = (tval * -1 - math.sqrt(detval)) / (2 * tqu)
					if root1 > 0 and root2 > 0:
						if root1 > root2:
							print(root2)
						else:
							print(root1)
					elif root1 < 0 and root2 > 0:
						print(root2)
					elif root1 > 0 and root2 < 0:
						print(root1)
					else:
						print()