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: interview

Starter code:

Solutions:
# cook your dish here
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)