/* O(N^3 log N) time solution

We need to find a shortest path, but we must stay within range d of towers.
This means that the terrain we can visit is the intersection of a set of
circles with radius d and the center the location of a tower.

Our shortest path will only change directions on an intersection point
between circles and only on the boundary of the reachable terrain.
(TODO: this may need to be explained further)

Therefore, we can solve the problem as follows:
 1. take all intersection points between circles (at most N^2 in total)
 2. throw out all points that lie strictly inside one of the circles
   (at most 2*N remain -- TODO: prove this)
 3. add the starting and goal location
 4. add a straight edge between every pair of points if the line segment
    between these points does not lie outside the reachable terrain
    (i.e. every point on the line segment lies inside or on the edge of
    at least one circle)
 5. apply Dijkstra's algorithm to find the shortest path from start to
    goal (if one exists).

Step 4 is the bottle neck here, since for every potential edge we need
to check each circle for intersection, producing O(N) intersection points,
which need to be sorted, yielding a time complexity of O(N^3 log N).

Our shortest path will consist of consecutive straight line segments,
the end points of which are one of:
 - the start location
 - the goal location
 - an intersection point between 


Rationale:
 - take all intersection point between circles: at most N^2.
 - remove all intersection points that lie strictly inside another circle:
   at most N points remain.
 - 
*/

#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <utility>
#include <vector>
#include <queue>
using namespace std;

const double eps = 1e-9;
const double inf = numeric_limits<double>::infinity();

inline bool eq(double x, double y) { return abs(x - y) < eps; }
inline bool lt(double x, double y) { return x < y - eps; }

static bool svg = false, edges = false, fw = false;

struct Point
{
    double x, y;

    Point() { }
    Point(double x, double y) : x(x), y(y) { }

    bool operator< (const Point &p) const {
        return lt(x, p.x) || eq(x, p.x) && lt(y, p.y);
    }

    bool operator== (const Point &p) const {
        return eq(x, p.x) && eq(y, p.y);
    }

    Point operator+ (const Point &p) const {
        return Point(x + p.x, y + p.y);
    }

    Point operator- (const Point &p) const {
        return Point(x - p.x, y - p.y);
    }

    Point operator* (double f) const {
        return Point(f*x, f*y);
    }

    double lensq() const { return x*x + y*y; }
    double len() const { return sqrt(lensq()); }
};

/* Calculcates wether a circle with center 'c' and radius 'r' intersects a
line defined by v + k*dv, and, if so, sets i1 and i2 so that the
intersection points are at v + i*dv and v + k*dv. */
bool intersect(
    const Point &c, double r,
    const Point &v, const Point &dv,
    double &i1, double &i2 )
{
    Point dc(-dv.y, dv.x);          /* define dc as vector perpendicular to dv */
    dc = dc*(1.0/dc.len());         /* rescale dc to unit length */

    double det = dc.y*dv.x - dc.x*dv.y,
        f = (dc.x*(v.y - c.y) - dc.y*(v.x - c.x))/det,
        g = (dv.x*(v.y - c.y) - dv.y*(v.x - c.x))/det;
    /* intersection == v + dv*f == c + dc*g */

    if(abs(g) > r)
        return false;

    double m = (sqrt(r*r - g*g))/dv.len();
    i1 = f - m;
    i2 = f + m;
    return true;
}

Point read_location()
{
    Point p;
    if(!(cin >> p.x >> p.y))
        throw "could not read location";
    if(p.x < 1 || p.x > 1000 || p.y < 1 || p.y > 1000)
        throw "coordinates out of range";
    return p;
}

void run()
{
    int D, T;
    vector<Point> towers, points;
    Point start, goal;

    if(!(cin >> D >> T))
        throw "could not read D and T";
    if(D < 1 || D > 1000)
        throw "D out of range";
    if(T < 1 || T > 200)
        throw "T out of range";

    start = read_location();
    goal  = read_location();
    bool start_ok = false;
    for(int t = 0; t < T; ++t)
    {
        towers.push_back(read_location());
        if(find(towers.begin(), towers.end(), towers.back()) != towers.end() - 1)
            throw "duplicate tower location";

        if((towers.back() - start).lensq() <= D*D)
            start_ok = true;
    }
    if(!start_ok)
        throw "starting location not in range of any tower";

    /* Compute intersection points */
    for(int s = 0; s < T; ++s)
    {
        for(int t = s + 1; t < T; ++t)
        {
            Point v = (towers[s] + towers[t])*0.5,
                dv(towers[s].y - v.y, v.x - towers[s].x);
            double i, j;
            if(intersect(towers[s], D, v, dv, i, j))
            {
                points.push_back(v + dv*i);
                points.push_back(v + dv*j);
            }
        }
    }

    /* Remove duplicates */
    sort(points.begin(), points.end());
    points.erase(unique(points.begin(), points.end()), points.end());

    /* Remove points that lie inside another circle */
    {
        vector<Point> new_points;
        for( vector<Point>::const_iterator i = points.begin();
            i != points.end(); ++i )
        {
            for(int t = 0; t < T; ++t)
                if(lt((*i - towers[t]).lensq(), D*D))
                    goto skip_point;
            new_points.push_back(*i);
        skip_point: continue;
        }
        points.swap(new_points);
    }

    /* Add start and goal points */
    points.push_back(start);
    points.push_back(goal);

    /* Determine permissible edges */
    int N = int(points.size());
    vector<double> dist(N*N, inf);
    for(int i = 0; i < N; ++i)
    {
        for(int j = i + 1; j < N; ++j)
        {
            /* Determine which parts of the line overlap with a circle */
            vector<pair<double, double> > ranges;
            Point delta = points[j] - points[i];
            for(int t = 0; t < T; ++t)
            {
                double x, y;
                if(intersect(towers[t], D, points[i], delta, x, y))
                {
                    if(x > y)
                        swap(x, y);
                    if(lt(x, 1) && lt(0, y))
                        ranges.push_back(make_pair(x, y));
                }
            }

            /* Verify that the entire edge has been covered */
            sort(ranges.begin(), ranges.end());
            double l = 0;
            for( vector<pair<double, double> >::const_iterator it = ranges.begin();
                it != ranges.end(); ++it )
            {
                if(lt(l, it->first))
                    break;
                l = max(l, it->second);
            }
            if(!lt(l, 1))
                dist[i*N + j] = dist[j*N + i] = delta.len();    /* Add edge! */
        }
    }

    vector<double> shortest(N, inf);
    if (fw)
    {
        /* Find shortest path using Floyd-Warshall algorithm */
        vector<double> M = dist;
        for (int k = 0; k < N; ++k)
            for (int i = 0; i < N; ++i)
                for (int j = 0; j < N; ++j)
                    M[i*N + j] = min(M[i*N + j], M[i*N + k] + M[k*N + j]);
        for (int n = 0; n < N; ++n)
            shortest[n] = M[(N-2)*N + n];
    }
    else
    {
        /* Find shortest paths using Dijkstra's algorithm (O(N*log(N)) */
        priority_queue<pair<double,int>, vector<pair<double,int> >, greater<pair<double,int> > > pq;
        shortest[N - 2] = 0;
        pq.push(make_pair(0.0, N - 2));
        while (!pq.empty())
        {
            double d = pq.top().first;
            int n = pq.top().second;
            pq.pop();
            if (d != shortest[n])
                continue;
            for (int m = 0; m < N; ++m)
                if (d + dist[n*N + m] < shortest[m])
                {
                    shortest[m] = d + dist[n*N + m];
                    pq.push(make_pair(shortest[m], m));
                }
        }
    }
    cout << setprecision(15) << showpoint;
    cout << (shortest[N - 1] < inf ? shortest[N - 1] : - 1) << endl;

    /* Write to SVG file */
    void write_svg( int D,
        const vector<Point> &towers, const vector<Point> &points,
        const vector<double> &shortest, const vector<double> &dist);
    if (svg)
        write_svg(D, towers, points, shortest, dist);
}


#include <fstream>
#include <sstream>
#include <string>
#include <cstdio>
void write_svg( int D,
    const vector<Point> &towers, const vector<Point> &points,
    const vector<double> &shortest, const vector<double> &dist )
{
    char filename[64];
    static int file_num = 0;

    sprintf(filename, "%02d.svg", file_num++);
    ofstream svg(filename);

    double minx = inf, miny = inf, maxx = 0, maxy = 0;
    for(int t = 0; t < int(towers.size()); ++t)
    {
        maxx = max(maxx, towers[t].x + D), maxy = max(maxy, towers[t].y + D);
        minx = min(minx, towers[t].x - D), miny = min(miny, towers[t].y - D);
    }

    double w = maxx - minx + 1, h = maxy - miny + 2;
    svg << "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"yes\"?>\n\
<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" \
version=\"1.1\" width=\"" << w << "\" height=\"" << h << "\">\
<g transform=\"translate(0, " << h << ") scale(1, -1) translate(" <<
(-minx + 1) << "," << (-miny + 1) << ")\">\n";

    for(int t = 0; t < int(towers.size()); ++t)
        svg << "<circle cx=\"" << towers[t].x << "\" cy=\"" << towers[t].y
            << "\" r=\"" << D << "\" fill=\"none\" stroke=\"blue\" stroke-width=\"0.2\" opacity=\".3\"/>\n";

    const int N = int(points.size());

    // Reconstruct path
    vector<bool> path(N*N);
    if(shortest[N - 1] < inf)
    {
        int p = N - 1, q;
        while (p != N - 2)
        {
            for (q = 0; q < N; ++q)
                if (q != p && shortest[q] + dist[q*N + p] < shortest[p] + eps)
                    break;
            path[p*N + q] = path[q*N + p] = true;
            p = q;
        }
    }

    for(int i = 0; i < N; ++i)
        for(int j = i + 1; j < N; ++j)
            if(dist[N*i + j] < inf)
            {
                if (!edges && !path[N*i + j])
                    continue;
                Point delta = points[j] - points[i];
                svg << "<line x1=\"" << points[i].x << "\" y1=\"" << points[i].y
                    << "\" x2=\"" << points[j].x << "\" y2=\"" << points[j].y
                    << "\" stroke-width=\"" << (path[N*i + j] ? 0.2 : 0.05) << "\""
                    << " stroke=\"" << (path[N*i + j] ? "red" : "black") << "\""
                    << "/>\n";
            }

    for(int i = 0; i < N; ++i)
        svg << "<circle cx=\"" << points[i].x << "\" cy=\"" << points[i].y
                << "\" r=\"0.15\" fill=\"black\"/>\n";
    svg << "<circle cx=\"" << points[N-2].x << "\" cy=\"" << points[N-2].y
            << "\" r=\"0.5\" fill=\"green\"/>\n";
    svg << "<circle cx=\"" << points[N-1].x << "\" cy=\"" << points[N-1].y
            << "\" r=\"0.5\" fill=\"blue\"/>\n";

    svg << "</g></svg>\n";
}

int main(int argc, char *argv[])
{
    int runs, r;
    cin >> runs;


    for (int a = 1; a < argc; ++a)
    {
        string arg(argv[a]);
        if (arg == "--svg")
            svg = true;
	else
        if (arg == "--edges")
            edges = true;
	else
        if (arg == "--fw")
            fw = true;
	else
	{
	    cout << "Unrecognized argument: " << arg << endl;
	    return 1;
	}
    }

    try {
        for(r = 0; r < runs; ++r)
            run();
    } catch(const char *error) {
        std::cerr << "Error during case " << r << ": " << error << std::endl;
        return 1;
    }
}
