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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nepi=10**-2\ndef vision(t):\n a1=x0+(dx*t)-x1\n a2=y0+(dy*t)-y1\n a3=z0+(dz*t)-z1\n b=4*((a1*d1)+(a2*d2)+(a3*d3))*((a1*d1)+(a2*d2)+(a3*d3))\n a=4*((a1*a1)+(a2*a2)+(a3*a3))\n value=(b-(a*c))\n return value\nxrange=range\nfor _ in range(int(input())):\n x1,y1,z1,x0,y0,z0,dx,dy,dz,cx,cy,cz,r=list(map(int,input().split()))\n d1=x1-cx\n d2=y1-cy\n d3=z1-cz\n c=(d1*d1)+(d2*d2)+(d3*d3)-(r*r)\n low=0\n high=10**9+1\n while low<(high-10**-6):\n  mid=low+(high-low)*1.0/2;\n  value=vision(mid);\n  if abs(value)<=epi:\n   break;\n  elif value>0:\n   low=mid;\n  else:\n   high=mid;\n print(mid)\n \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13383