#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using i64=long long;
using u64=unsigned long long;
using i128=__int128;
#define equals(a,b) (fabs((a) - (b))< eps ) //精度内相等
const double inf = 1e20; //最大值
const double eps = 1e-8; //精度
const double pi = acos(-1.0);
const int maxp = 2010; //注意题目范围
double truevalue(double x) {// 去0
	if (fabs(x)<eps) return 0;
	else return x;
}
int sgn(double x){// 判断正负0
    if(fabs(x)<eps) return 0;
    if(x<0) return -1;
    else return 1;
}
int dcmp(double x,double y){// 比较数字
    if(fabs(x-y)<eps) return 0;
    if(x<y) return -1;
    return 1;
}
//点，向量
template<class T>
struct Point{
    T x,y;
    Point(const T &x_=0,const T &y_=0):x(x_),y(y_){}
    template<class U>
    operator Point<U>(){
        return Point<U>(U(x),U(y));
    }
    //返回长度
	T len() {
		return hypot(x, y);
	}
    T len2(){
        return x*x+y*y;
    }
    Point<T> trunc(T r) {//转化为长度为r的同向向量
		T l = len();
		if (!sgn(l)) return *this;
		r /= l;
		return Point<T>(x * r, y * r);
	}
    //逆时针旋转 90 度
	Point<T> rotleft() {
		return Point<T>(-y, x);
	}
    //顺时针旋转 90 度
	Point<T> rotright() {
		return Point<T>(y, -x);
	}
    //绕着 p 点逆时针旋转 angle
	Point<T> rotate(Point<T> p, T angle) {
		Point<T> v = (*this) - p;
		T c = cos(angle), s = sin(angle);
		return Point<T>(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);
	}
	Point<T> pointtruevalue() {//精度值以内
		Point<T> a;
		a.x = truevalue(x);
		a.y = truevalue(y);
		return a;
	}
    // 以下均为重载运算符
    bool operator==(const Point<T> &a)const{
        return sgn(x-a.x)==0&&sgn(y-a.y)==0;
    }
    bool operator!=(const Point<T> &a)const{
        return sgn(x-a.x)!=0||sgn(y-a.y)!=0;
    }
    Point<T> &operator+=(const Point<T> &a)&{
        x+=a.x;
        y+=a.y;
        return *this;
    }
    Point<T> &operator-=(const Point<T> &a)&{
        x-=a.x;
        y-=a.y;
        return *this;
    }
    Point<T> &operator*=(const T &a)&{
        x*=a;
        y*=a;
        return *this;
    }
    Point<T> &operator/=(const T &a)&{
        x/=a;
        y/=a;
        return *this;
    }
    Point<T> operator-()const{
        return Point<T>(-x,-y);
    }
    friend Point<T> operator+(Point<T> a, const Point<T> &b) {
        return a+=b;
    }
    friend Point<T> operator-(Point<T> a, const Point<T> &b) {
        return a -= b;
    }
    friend Point<T> operator*(Point<T> a, const T &b) {
        return a *= b;
    }
    friend Point<T> operator/(Point<T> a, const T &b) {
        return a /= b;
    }
    friend Point<T> operator*(const T &a, Point<T> b) {
        return b *= a;
    }
    friend std::istream &operator>>(std::istream &is, Point<T> &p) {
        return is >> p.x >> p.y;
    }
    friend std::ostream &operator<<(std::ostream &os, const Point<T> &p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};
template<class T>// 点的相对位置排序
int sgn(const Point<T> &a) {
    return a.y > 0 || (a.y == 0 && a.x > 0)? 1 : -1;
}
template<class T>//点乘
T dot(const Point<T> &a, const Point<T> &b) {
    return a.x * b.x + a.y * b.y;
}
template<class T>//叉乘
T cross(const Point<T> &a, const Point<T> &b) {
    return a.x * b.y - a.y * b.x;
}
template<class T>//叉乘
T cross(Point<T> &A, Point<T> &B, Point<T> &C) {
	return cross((B - A) , (C - A));
}
template<class T>//点乘
T dot(Point<T> &A, Point<T> &B, Point<T> &C) {
	return dot((B - A) , (C - A));
}
template<class T>//求pa与pb的夹角
double rad(const Point<T> &p,const Point<T> &a, const Point<T> &b){
    return fabs(atan2(fabs(cross((a - p),(b - p))), dot((a - p),(b - p))));
}
template<class T>// 求向量的夹角
T rad(Point<T> &a){
    return atan2(a.y,a.x);
}
template<class T>//向量长度平方
T square(const Point<T> &p) {
    return dot(p, p);
}
template<class T>//向量长度
double length(const Point<T> &p) {
    return std::sqrt(square(p));
}
template<class T>//单位向量
Point<T> norms(const Point<T> &p) {
    return p / length(p);
}
template<class T>//两点距离
double distance(const Point<T> &a, const Point<T> &b) {
    return length(a - b);
}
// 线
template<class T>
struct Line {
    Point<T> a;
    Point<T> b;
    Line(const Point<T> &a_ = Point<T>(), const Point<T> &b_ = Point<T>()) : a(a_), b(b_) {}
};
template<class T>// 投影向量
Point<T> projection(const Point<T> &p, const Line<T> &l) {
    return l.a + (l.b - l.a) * dot(l.b - l.a, p - l.a) / square((l.b - l.a));
}
template<class T>  // 点关于直线对称
Point<T> reflection(const Point<T> &p, const Line<T> &l) {
    return p + (projection(p, l) - p) * T(2);
}
template<class T>//线长度
double length(const Line<T> &l) {
    return length(l.a - l.b);
}
template<class T>//判断线是否平行，平行返回1
bool parallel(const Line<T> &l1, const Line<T> &l2) {
    return cross(l1.b - l1.a, l2.b - l2.a) == 0;
}
template<class T>//点到直线的距离
double distancePL(const Point<T> &p, const Line<T> &l) {
    return std::abs(cross(l.a - l.b, l.a - p)) / length(l);
}
template<class T>//点到线段的距离
double distancePS(const Point<T> &p, const Line<T> &l) {
    if (dot(p - l.a, l.b - l.a) < 0) {
        return distance(p, l.a);
    }
    if (dot(p - l.b, l.a - l.b) < 0) {
        return distance(p, l.b);
    }
    return distancePL(p, l);
}
template<class T>//判断一个点与直线的位置
int pointOnLine(const Point<T> &p, const Line<T> &l) { 
    T x=cross(l.b - l.a, p - l.a);
    if(sgn(x)>0) return 1;//左
    else if(sgn(x)<0) return 2;//右
    else return 0;//在线段上
}
template<class T>//判断点是否在线段上
bool pointOnSegment(const Point<T> &p, const Line<T> &l) {
    return cross(p - l.a, l.b - l.a) == 0 && std::min(l.a.x, l.b.x) <= p.x && p.x <= std::max(l.a.x, l.b.x)
        && std::min(l.a.y, l.b.y) <= p.y && p.y <= std::max(l.a.y, l.b.y);
}
template<class T>// 两直线的交点
Point<T> lineIntersection(const Line<T> &l1, const Line<T> &l2) {
    return l1.a + (l1.b - l1.a) * (cross(l2.b - l2.a, l1.a - l2.a) / cross(l2.b - l2.a, l1.a - l1.b));
}
template<class T>//点是否在多边形内部
bool pointInPolygon(const Point<T> &a, const std::vector<Point<T>> &p) {
    int n = p.size();
    for (int i = 0; i < n; i++) {
        if (pointOnSegment(a, Line(p[i], p[(i + 1) % n]))) {
            return true;
        }
    }
    int t = 0;
    for (int i = 0; i < n; i++) {
        auto u = p[i];
        auto v = p[(i + 1) % n];
        if (u.x < a.x && v.x >= a.x && pointOnLineLeft(a, Line(v, u))) {
            t ^= 1;
        }
        if (u.x >= a.x && v.x < a.x && pointOnLineLeft(a, Line(u, v))) {
            t ^= 1;
        }
    }
    return t == 1;
}
template<class T>// 两条线段
// 0 : 完全不相交
// 1 : 严格相交，交点在线段内部
// 2 : 线段部分重叠
// 3 : 线段在端点处相交
std::tuple<int, Point<T>, Point<T>> segmentIntersection(const Line<T> &l1, const Line<T> &l2) {
    if (std::max(l1.a.x, l1.b.x) < std::min(l2.a.x, l2.b.x)) {
        return {0, Point<T>(), Point<T>()};
    }
    if (std::min(l1.a.x, l1.b.x) > std::max(l2.a.x, l2.b.x)) {
        return {0, Point<T>(), Point<T>()};
    }
    if (std::max(l1.a.y, l1.b.y) < std::min(l2.a.y, l2.b.y)) {
        return {0, Point<T>(), Point<T>()};
    }
    if (std::min(l1.a.y, l1.b.y) > std::max(l2.a.y, l2.b.y)) {
        return {0, Point<T>(), Point<T>()};
    }
    if (cross(l1.b - l1.a, l2.b - l2.a) == 0) {
        if (cross(l1.b - l1.a, l2.a - l1.a) != 0) {
            return {0, Point<T>(), Point<T>()};
        } else {
            auto maxx1 = std::max(l1.a.x, l1.b.x);
            auto minx1 = std::min(l1.a.x, l1.b.x);
            auto maxy1 = std::max(l1.a.y, l1.b.y);
            auto miny1 = std::min(l1.a.y, l1.b.y);
            auto maxx2 = std::max(l2.a.x, l2.b.x);
            auto minx2 = std::min(l2.a.x, l2.b.x);
            auto maxy2 = std::max(l2.a.y, l2.b.y);
            auto miny2 = std::min(l2.a.y, l2.b.y);
            Point<T> p1(std::max(minx1, minx2), std::max(miny1, miny2));
            Point<T> p2(std::min(maxx1, maxx2), std::min(maxy1, maxy2));
            if (!pointOnSegment(p1, l1)) {
                std::swap(p1.y, p2.y);
            }
            if (p1 == p2) {
                return {3, p1, p2};
            } else {
                return {2, p1, p2};
            }
        }
    }
    auto cp1 = cross(l2.a - l1.a, l2.b - l1.a);
    auto cp2 = cross(l2.a - l1.b, l2.b - l1.b);
    auto cp3 = cross(l1.a - l2.a, l1.b - l2.a);
    auto cp4 = cross(l1.a - l2.b, l1.b - l2.b);
    
    if ((cp1 > 0 && cp2 > 0) || (cp1 < 0 && cp2 < 0) || (cp3 > 0 && cp4 > 0) || (cp3 < 0 && cp4 < 0)) {
        return {0, Point<T>(), Point<T>()};
    }
    
    Point p = lineIntersection(l1, l2);
    if (cp1 != 0 && cp2 != 0 && cp3 != 0 && cp4 != 0) {
        return {1, p, p};
    } else {
        return {3, p, p};
    }
}
template<class T>//直线和线段
//2 规范相交
//1 非规范相交(部分重叠，端点相交)
//0 不相交
int linecrossseg(const Line<T> &l1,const Line<T> &l2){
    int d1 = sgn(cross((l1.b - l1.a),(l2.a-l1.a)));
    int d2 = sgn(cross((l1.b - l1.a),(l2.b - l1.a)));
    if ((d1 ^ d2) == -2) return 2;
    return (d1 == 0 || d2 == 0);
}
template<class T> // 两条直线
//0 平行
//1 重合
//2 相交
int linecrossline(const Line<T> &l1,const Line<T> &l2){
    double a1 = (l2.b - l2.a) ^ (l1.a - l2.a);
		double a2 = (l2.b - l2.a) ^ (l1.b - l2.a);
		return Point((l1.a.x * a2 - l1.b.x * a1) / (a2 - a1), (l1.a.y * a2 - l1.b.y * a1) / (a2 - a1
			));
}
template<class T>//两条线段的最短距离
double distanceSS(const Line<T> &l1, const Line<T> &l2) {
    if (std::get<0>(segmentIntersection(l1, l2)) != 0) {
        return 0.0;
    }
    return std::min({distancePS(l1.a, l2), distancePS(l1.b, l2), distancePS(l2.a, l1), distancePS(l2.b, l1)});
}
template<class T>//线段是否在多边形内部
bool segmentInPolygon(const Line<T> &l, const std::vector<Point<T>> &p) {
    int n = p.size();
    if (!pointInPolygon(l.a, p)) {
        return false;
    }
    if (!pointInPolygon(l.b, p)) {
        return false;
    }
    for (int i = 0; i < n; i++) {
        auto u = p[i];
        auto v = p[(i + 1) % n];
        auto w = p[(i + 2) % n];
        auto [t, p1, p2] = segmentIntersection(l, Line(u, v));
        
        if (t == 1) {
            return false;
        }
        if (t == 0) {
            continue;
        }
        if (t == 2) {
            if (pointOnSegment(v, l) && v != l.a && v != l.b) {
                if (cross(v - u, w - v) > 0) {
                    return false;
                }
            }
        } else {
            if (p1 != u && p1 != v) {
                if (pointOnLineLeft(l.a, Line(v, u))
                    || pointOnLineLeft(l.b, Line(v, u))) {
                    return false;
                }
            } else if (p1 == v) {
                if (l.a == v) {
                    if (pointOnLineLeft(u, l)) {
                        if (pointOnLineLeft(w, l)
                            && pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    } else {
                        if (pointOnLineLeft(w, l)
                            || pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    }
                } else if (l.b == v) {
                    if (pointOnLineLeft(u, Line(l.b, l.a))) {
                        if (pointOnLineLeft(w, Line(l.b, l.a))
                            && pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    } else {
                        if (pointOnLineLeft(w, Line(l.b, l.a))
                            || pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    }
                } else {
                    if (pointOnLineLeft(u, l)) {
                        if (pointOnLineLeft(w, Line(l.b, l.a))
                            || pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    } else {
                        if (pointOnLineLeft(w, l)
                            || pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    }
                }
            }
        }
    }
    return true;
}
template<class T>//构建上下两个凸包
auto getpart(std::vector<Point<T>> p) {
    std::sort(p.begin(), p.bnd(),
        [&](auto a, auto b) {
            return a.x < b.x || (a.x == b.x && a.y < b.y);
        });
    
    std::vector<Point<T>> hi, lo;
    for (auto p : p) {
        while (hi.size() > 1 && cross(hi.back() - hi[hi.size() - 2], p - hi.back()) >= 0) {
            hi.pop_back();
        }
        while (!hi.empty() && hi.back().x == p.x) {
            hi.pop_back();
        }
        hi.push_back(p);
        while (lo.size() > 1 && cross(lo.back() - lo[lo.size() - 2], p - lo.back()) <= 0) {
            lo.pop_back();
        }
        if (lo.empty() || lo.back().x < p.x) {
            lo.push_back(p);
        }
    }
    return std::make_pair(hi, lo);
}
template<class T>//完整凸包
vector<Point<T>> convexhull(vector<Point<T>> a) {
    int n = a.size();
    sort(a.begin(), a.end(), [&](auto a, auto b) {
        if (a.x !=b.x) {
            return a.x < b.x;
        }
        return a.y < b.y;
    });
   
    vector<Point<T>> b;
    for (int i = 0; i < n; i++) {
        while (b.size() > 1 && sgn(cross(b[(int) b.size() - 1] - b[(int) b.size() - 2], a[i] - b[(int) b.size() - 2])) <= 0) {
            b.pop_back();
        }
        b.push_back(a[i]);
    }
    int k = b.size();
    for (int i = n - 2; i >= 0; i--) {
        while (b.size() > k && sgn(cross(b[(int) b.size() - 1] - b[(int) b.size() - 2], a[i] - b[(int) b.size() - 2])) <= 0) {
            b.pop_back();
        }
        b.push_back(a[i]);        
    }
    b.pop_back();
    return b;
}
template<class T> //包含边上点凸包
vector<Point<T>> Andrew(vector<Point<T>> a)   // Andrew 算法求凸包  包括边上的点
{
    int n = a.size();
    sort(a.begin(), a.end(), [&](auto a, auto b) {
        if (a.x !=b.x) {
            return a.x < b.x;
        }
        return a.y < b.y;
    });
    sort(a, a + n);
    vector<Point<T>> b;
    for (int i = 0; i < n; i++)
    {
        while (b.size() > 1 && cross(b[b.size() - 2], b[b.size() - 1], a[i]) < 0) b.pop_back();
        b.push_back(a[i]);
    }
    int k = b.size();
    for (int i = n - 2; i >= 0; i--)
    {
        while (b.size()> k && cross(b[b.size() - 2], b[b.size() - 1], a[i]) < 0) b.pop_back();
        b.push_back(a[i]);
    }
    if (n > 1) b.pop_back();
    return b;
}
// 圆
template<class T> 
struct Circle{
    Point<T> p;
    T r;
    Circle() {}
	Circle(Point<T> _p, T _r) {
		p = _p;
		r = _r;
	}
    bool operator == (Circle v) {
		return (p == v.p) && sgn(r - v.r) == 0;
	}
	bool operator < (Circle v)const {
		return ((p < v.p) || ((p == v.p) && sgn(r - v.r) < 0));
	}
    //面积
	T area() {
		return pi * r * r;
	}
	//周长
	T circumference() {
		return 2.0 * pi * r;
	}
};
template<class T>//三点共圆求圆
Circle<T> circlecenter(Point<T> a,Point<T> b,Point<T> c){
    long double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2.0;
    long double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2.0;
    long double d = a1 * b2 - a2 * b1;
    Point<T> p=Point<T>(a.x + (c1 * b2 - c2 * b1) / d, a.y + (a1 * c2 - a2 * c1) / d);
    T r=distance(a,p);
    return {p,r};
}
template<class T> //三角形的外接圆
Circle<T> Circumcircle(Point<T> a, Point<T> b, Point<T> c) {
    Line<T> u = Line<T>((a + b) / 2, ((a + b) / 2) + ((b - a).rotleft()));
    Line<T> v = Line<T>((b + c) / 2, ((b + c) / 2) + ((c - b).rotleft()));
    Point<T> p = lineIntersection(u,v);
    T r = distance(a,p);
    return {p,r};
}
template<class T>// 三角形内切圆
Circle<T> InscribedCircle(Point<T> A, Point<T> B, Point<T> C){
    T a = distance(B,C);
    T b = distance(A,C);
    T c = distance(A,B);
    Line AB(A, B);
    Point<T> p = (A * a + B * b + C * c) / (a + b + c);
    T r = distancePL(AB,p);
    return {p,r};
}
template<class T>//点和圆的关系
//0 圆外
//1 圆上
//2 圆内
int relation(Circle<T> &l,Point<T> &b) {
    T dst = distance(b,l.p);
    if (sgn(dst - l.r) < 0) return 2;
    else if (sgn(dst - l.r) == 0) return 1;
    return 0;
}
template<class T> //线段和圆的关系
//比较的是圆心到线段的距离和半径的关系
int relationseg(Circle<T> &a,Line<T> &v) {
    T dst = istancePS(a.p,v);
    if (sgn(dst - a.r) < 0) return 2;
    else if (sgn(dst - a.r) == 0) return 1;
    return 0;
}
template<class T> //直线和圆的关系
//比较的是圆心到直线的距离和半径的关系
int relationline(Circle<T> &a,Line<T> &v) {
    T dst = distancePL(a.p,v);
    if (sgn(dst - a.r) < 0) return 2;
    else if (sgn(dst - a.r) == 0) return 1;
    return 0;
}
template<class T> //两圆的关系
//5 相离
//4 外切
//3 相交
//2 内切
//1 内含
//需要  distance
int relationcircle(Circle<T> &v,Circle<T> &a) {
    T d = distance(a.p,v.p);
    if (sgn(d - a.r - v.r) > 0) return 5;
    if (sgn(d - a.r - v.r) == 0) return 4;
    T l = fabs(a.r - v.r);
    if (sgn(d - a.r - v.r) < 0 && sgn(d - l) > 0) return 3;
    if (sgn(d - l) == 0) return 2;
    if (sgn(d - l) < 0) return 1;
}
template<class T> //求两个圆的交点，返回 0 表示没有交点，返回 1 是一个交点，2 是两个交点
//需要 relationcircle
int pointcrosscircle(Circle<T> &a,Circle<T> &v, Point<T>& p1, Point<T>& p2) {
    int rel = relationcircle(a,v);
    if (rel == 1 || rel == 5)return 0;
    T d = distance(a.p,v.p);
    T l = (d * d + a.r * a.r - v.r * v.r) / (2 * d);
    T h = sqrt(a.r * a.r - l * l);
    Point<T> tmp = a.p + (v.p - a.p).trunc(l);
    p1 = tmp + ((v.p - a.p).rotleft().trunc(h));
    p2 = tmp + ((v.p - a.p).rotright().trunc(h));
    if (rel == 2 || rel == 4)
        return 1;
    return 2;
}
template<class T>//求直线和圆的交点，返回交点个数
int pointcrossline(Circle<T> &b,Line<T> &v, Point<T>& p1, Point<T>& p2) {
    if (!relationline(b,v)) return 0;
    Point<T> a = projection(b.p,v);
    T d = distancePL(b.p,v);
    d = sqrt(b.r * b.r - d * d);
    if (sgn(d) == 0) {
        p1 = a;
        p2 = a;
        return 1;
    }
    p1 = a + (v.b - v.s).trunc(d);
    p2 = a - (v.e - v.s).trunc(d);
    return 2;
}
template<class T> //得到过 a,b 两点，半径为 r1 的两个圆
int gercircle(Point<T> &a, Point<T> &b, T r1, Circle<T>& c1, Circle<T>& c2) {
    Circle<T> x(a, r1), y(b, r1);
    int t = pointcrosscircle(x,y, c1.p, c2.p);
    if (!t) return 0;
    c1.r = c2.r = r1;
    return t;
}
template<class T>//得到与直线 u 相切，过点 q, 半径为 r1 的圆 返回个数，以及每个圆
int getcircle(Line<T> &u, Point<T> &q, T r1, Circle<T> &c1, Circle<T> &c2) {
    T dis = distancePL(q,u);
    if (sgn(dis - r1 * 2) > 0) return 0;
    if (sgn(dis) == 0) {
        c1.p = q + ((u.b - u.a).rotleft().trunc(r1));
        c2.p = q + ((u.b - u.a).rotright().trunc(r1));
        c1.r = c2.r = r1;
        return 2;
    }

    Line<T> u1 = Line<T>((u.a + (u.b - u.a).rotleft().trunc(r1)), (u.b + (u.b - u.a).rotleft().trunc(r1)));
    Line<T> u2 = Line<T>((u.a + (u.b - u.a).rotright().trunc(r1)), (u.b + (u.b - u.a).rotright().trunc(r1)));
    Circle<T> cc = Circle(q, r1);
    Point<T> p1, p2;
    if (!pointcrossline(cc,u1, p1, p2))
        pointcrossline(cc,u2, p1, p2);
    c1 = Circle(p1, r1);
    if (p1 == p2) {
        c2 = c1;
        return 1;
    }
    c2 = Circle(p2, r1);
    return 2;
}
template<class T> //同时与直线 u,v 相切，半径为 r1 的圆
int getcircle(Line<T> &u, Line<T> &v, T r1, Circle<T>& c1, Circle<T>& c2, Circle<T>& c3, Circle<T>& c4) {
    if (parallel(u,v))return 0;//两直线平行
    Line<T> u1 = Line<T>(u.s + (u.e - u.s).rotleft().trunc(r1), u.e + (u.e - u.s).rotleft().trunc(r1));
    Line<T> u2 = Line<T>(u.s + (u.e - u.s).rotright().trunc(r1), u.e + (u.e - u.s).rotright().trunc(r1));
    Line<T> v1 = Line<T>(v.s + (v.e - v.s).rotleft().trunc(r1), v.e + (v.e - v.s).rotleft().trunc(r1));
    Line<T> v2 = Line<T>(v.s + (v.e - v.s).rotright().trunc(r1), v.e + (v.e - v.s).rotright().trunc(r1));
    c1.r = c2.r = c3.r = c4.r = r1;
    c1.p = lineIntersection(u1,v1);
    c2.p = lineIntersection(u1,v2);
    c3.p = lineIntersection(u2,v1);
    c4.p = lineIntersection(u2,v2);
    return 4;
}
template<class T>//同时与不相交圆 cx,cy 相切，半径为 r1 的圆
int getcircle(Circle<T> &cx, Circle<T> &cy, T r1, Circle<T>& c1, Circle<T>& c2) {
    Circle<T> x(cx.p, r1 + cx.r), y(cy.p, r1 + cy.r);
    int t =pointcrosscircle(x,y, c1.p, c2.p);
    if (!t) return 0;
    c1.r = c2.r = r1;
    return t;
}
template<class T> //过一点作圆的切线 (先判断点和圆的关系)
int tangentline(Circle<T> &a,Point<T> &q, Line<T> &u, Line<T> &v) {
    int x = relation(a,q);
    if (x == 2) return 0;
    if (x == 1) {
        u = Line<T>(q, q + (q - a.p).rotleft());
        v = u;
        return 1;
    }
    T d = distance(a.p,q);
    T l = a.r * a.r / d;
    T h = sqrt(a.r * a.r - l * l);
    u = Line<T>(q, a.p + ((q - a.p).trunc(l) + (q - a.p).rotleft().trunc(h)));
    v = Line<T>(q, a.p + ((q - a.p).trunc(l) + (q - a.p).rotright().trunc(h)));
    return 2;
}
template<class T> //求两圆相交的面积
T areacircle(Circle<T> &d,Circle<T> &v)
{
    int rel = relationcircle(d,v);
    if (rel >= 4) return 0.0;
    if (rel <= 2) return min(d.area(), v.area());
    T a = distance(d.p,v.p), b = a.r, c = v.r;
    T cta1 = acos((a * a + b * b - c * c) / 2 / (a * b)),
        cta2 = acos((a * a + c * c - b * b) / 2 / (a * c));
    T s1 = d.r * d.r * cta1 - d.r * d.r * sin(cta1) * (a * a + b * b - c * c) / 2 / (a * b);
    T s2 = v.r * v.r * cta2 - v.r * v.r * sin(cta2) * (a * a + c * c - b * b) / 2 / (a * c);
    return s1 + s2;
}
template<class T> //求圆和三角形 pab 的相交面积
T areatriangle(Circle<T> &v,Point<T> &a, Point<T> &b) {
    if (sgn(cross((v.p - a),(v.p - b))) == 0) return 0.0;
    Point<T> q[5];
    int len = 0;
    q[len++] = a;
    Line<T> l(a, b);
    Point<T> p1, p2;
    if (pointcrossline(v,l, q[1], q[2]) == 2) {
        if (sgn(dot((a - q[1]),(b - q[1]))) < 0) q[len++] = q[1];
        if (sgn(dot((a - q[2]),(b - q[2]))) < 0) q[len++] = q[2];
    }
    q[len++] = b;
    if (len == 4 && sgn(dot((q[0] - q[1]),(q[2] - q[1]))) > 0) swap(q[1], q[2]);
    T res = 0;
    for (int i = 0; i < len - 1; i++) {
        if (relation(v,q[i]) == 0 || relation(v,q[i + 1]) == 0) {
            T arg = rad(v.p,q[i], q[i + 1]);
            res += v.r * v.r * arg / 2.0;
        }
        else {
            res += fabs(cross((q[i] - v.p),(q[i + 1] - v.p))) / 2.0;
        }
    }
    return res;
}
template<class T> 	//两圆公切线 
//返回值为公切线条数，-1表示无数条公切线 
//线段起点都是大圆上切点，终点都是小圆v上切点（除了存在公切点时）
int tangentcircle(Circle<T> &a,Circle<T> &v, Line<T> l[4])
{
    int t = relationcircle(a,v);
    if (a.r < v.r)//使当前圆为半径大者 
        return tangentcircle(v,a,l);
    if (t == 5)//相离 
    {
        //特判半径相同情况 
        if (sgn(a.r - v.r) == 0)
        {
            l[0].a = a.p + (v.p - a.p).rotleft().trunc(a.r);
            l[0].b = l[0].a + v.p - a.p;
            l[1].a = a.p + (v.p - a.p).rotright().trunc(a.r);
            l[1].b = l[1].a + v.p - a.p;
            Point<T> q = (a.p + v.p) / 2;
            Line<T> t1, t2;
            tangentline(a,q, t1, t2);
            l[2].a = t1.b;
            l[3].a = t2.b;
            tangentline(v,q, t1, t2);
            l[2].b = t1.b;
            l[3].b = t2.b;
        }
        else
        {
            T d = distance(a.p,v.p);
            Point<T> q = v.p + (v.p - a.p).trunc(v.r * d / (a.r - v.r));
            Line<T> t1, t2;
            tangentline(a,q, t1, t2);
            l[0].a = t1.b;
            l[1].a = t2.b;
            tangentline(v,q, t1, t2);
            l[0].b = t1.b;
            l[1].b = t2.b;
            q = a.p + (v.p - a.p).trunc(a.r * d / (a.r + v.r));
            tangentline(a,q, t1, t2);
            l[2].a = t1.b;
            l[3].a = t2.b;
            tangentline(v,q, t1, t2);
            l[2].b = t1.b;
            l[3].b = t2.b;
        }
    }
    else if (t == 4)//外切
    {
        //特判半径相同情况 
        if (sgn(a.r - v.r) == 0)
        {
            l[0].a = a.p + (v.p - a.p).rotleft().trunc(a.r);
            l[0].b = l[0].a + v.p - a.p;
            l[1].a = a.p + (v.p - a.p).rotright().trunc(a.r);
            l[1].b = l[1].a + v.p - a.p;
            Point<T> q = (a.p + v.p) / 2;
            Line<T> t1, t2;
            tangentline(a,q, t1, t2);
            l[2] = t1;
        }
        else
        {
            T d = distance(a.p,v.p);
            Point<T> q = v.p + (v.p - a.p).trunc(v.r * d / (a.r - v.r));
            Line<T> t1, t2;
            tangentline(a,q, t1, t2);
            l[0].a = t1.b;
            l[1].a = t2.b;
            tangentline(v,q, t1, t2);
            l[0].b = t1.b;
            l[1].b = t2.b;
            q = a.p + (v.p - a.p).trunc(a.r);
            tangentline(a,q, t1, t2);
            l[2] = t1;
        }
    }
    else if (t == 3)//相交
    {
        //特判半径相同情况 
        if (sgn(a.r - v.r) == 0)
        {
            l[0].a = a.p + (v.p - a.p).rotleft().trunc(a.r);
            l[0].b = l[0].a + v.p - a.p;
            l[1].a = a.p + (v.p - a.p).rotright().trunc(a.r);
            l[1].b = l[1].a + v.p - a.p;
        }
        else
        {
            T d = distance(a.p,v.p);
            Point<T> q = v.p + (v.p - a.p).trunc(v.r * d / (a.r - v.r));
            Line<T> t1, t2;
            tangentline(a,q, t1, t2);
            l[0].a = t1.b;
            l[1].a = t2.b;
            tangentline(v,q, t1, t2);
            l[0].b = t1.b;
            l[1].b = t2.b;
        }
    }
    else if (t == 2)//内切
    {
        //特判半径相同情况 
        if (sgn(a.r - v.r) == 0)
            return -1;//无数条公切线
        else
        {
            Point<T> q = a.p + (v.p - a.p).trunc(a.r);
            Line<T> t1, t2;
            tangentline(a,q, t1, t2);
            l[0] = t1;
        }
    }
    //内含的情况直接返回0 
    return t - 1;
}
template<class T>// 极角排序
struct ACcmp {
    Point<T> o;
    ACcmp(const Point<T> &p0) {
        o = p0;
    }
    // 获取象限 (0, 1, 2, 3)
    int Quadrant(Point<T> p) { return sgn(p.y < 0) << 1 | sgn(p.x < 0) ^ sgn(p.y < 0); }
    // 比较函数
    bool operator()(const Point<T> &aa, const Point<T> &bb) {
        Point<T> p = aa - o, q = bb - o;
        int x = Quadrant(p), y = Quadrant(q);
        if (x == y) {
            if (sgn(cross(p,q)) == 0) return p.len2() < q.len2();
            return sgn(cross(p,q)) > 0;
        }
        return x < y;
    }
};
template<class T>//求最左下角的点 返回点和数组序号
Point<T> mipoint(vector<Point<T>> a,int& t) { //求最左下角的点 返回点和数组序号
    Point<T> mi(inf, inf);
    int n=a.size();
    for (int i = 0; i < n; i++)
    {
        if (dcmp(mi.y, a[i].y) > 0)mi.y = a[i].y, t = i;
        if (dcmp(mi.y, a[i].y) == 0)
            if (dcmp(mi.x, a[i].x) > 0) mi.x = a[i].x, t = i;

    }
    return mi;
}
template<class T> //判断是不是凸的
bool isconvex(vector<Point<T>> a) {
    bool s[3];
    memset(s, false, sizeof(s));
    int n=a.size();
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        int k = (j + 1) % n;
        s[sgn(cross((a[j] - a[i]) , (a[k] - a[i]))) + 1] = true;
        if (s[0] && s[2]) return false;
    }
    return true;
}
template<class T>// 直线切割多边形
vector<Point<T>> convexcut(Line<T> u,vector<Point<T>> a) {
    vector<Point<T>> b;
    int n=a.size();
    for (int i = 0; i < n; i++) {
        int d1 = sgn((u.b - u.a) ^ (a[i] - u.a));
        int d2 = sgn((u.b - u.a) ^ (a[(i + 1) % n] - u.a));
        if (d1 >= 0) b.push_back(a[i]);
        if (d1 * d2 < 0) b.push_back = lineIntersection(u,Line(a[i], a[(i + 1) % n]));
    }
    return b;
}
template<class T>// 周长
T getcircumference(vector<Point<T>> a) {
    T sum = 0;
    int n=a.size();
    for (int i = 0; i < n; i++) {
        sum += distance(a[i],a[(i + 1) % n]);
    }
    return sum;
}
template<class T>//面积
T getarea(vector<Point<T>> a) {
    T sum = 0;
    int n=a.size();
    for (int i = 0; i < n; i++) {
        sum += (cross(a[i] , a[(i + 1) % n]));
    }
    return fabs(sum) / 2;
}
template<class T> //得到方向
// 1 表示逆时针，0 表示顺时针
bool getdir(vector<Point<T>> a) {
    T sum = 0;
    int n=a.size();
    for (int i = 0; i < n; i++)
        sum += cross(a[i] , a[(i + 1) % n]);
    if (sgn(sum) > 0) return 1;
    return 0;
}
template<class T> //多边形和圆交的面积
double areacircle(Circle<T> &c,vector<Point<T>> &a) {
    T ans = 0;
    int n=a.size();
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        if (sgn(cross((a[j] - c.p) , (a[i] - c.p))) >= 0)
            ans += areatriangle(c,a[i], a[j]);
        else ans -= areatriangle(c,a[i], a[j]);
    }
    return fabs(ans);
}
template<class T> //多边形重心
Point<T> getbarycentre(vector<Point<T>> &a) {
    Point ret(0, 0);
    T area = 0;
    int n=a.size();
    for (int i = 1; i < n - 1; i++) {
        double tmp = cross((a[i] - a[0]),(a[i + 1] - a[0]));
        if (sgn(tmp) == 0)continue;
        area += tmp;
        ret.x += (a[0].x + a[i].x + a[i + 1].x) / 3 * tmp;
        ret.y += (a[0].y + a[i].y + a[i + 1].y) / 3 * tmp;
    }
    if (sgn(area)) ret = ret / area;
    return ret;
}
template<class T> //多边形和圆关系
// 2 圆完全在多边形内
// 1 圆在多边形里面，碰到了多边形边界
// 0 其它
int relationcircle(vector<Point<T>> &a,Circle<T> &c) {
    int x = 2;
    int n=a.size();
    if (pointInPolygon(c.p,a) != 1) return 0;//圆心不在内部
    for (int i = 0; i < n; i++) {
        Line<T> l(a[i],a[(i+1)%n]);
        if (relationseg(c,l) == 2) return 0;
        if (relationseg(c,l) == 1) x = 1;
    }
    return x;
}
template<class T>// 旋转卡壳，求凸包直径
T Rotating_calipers(vector<Point<T>> &a)
{
    if(a.size()==2) return distance(a[0],a[1]);
    T ans = 0;
    int n=a.size();
    int op = 0;
    for (int i = 0; i < n; i++)
    {
        while (cross(a[i], a[i + 1], a[op]) <= cross(a[i], a[i + 1], a[op + 1]))
            op = (op + 1) % n;
        ans = max(ans, max((a[i] - a[op]).len(), (a[i + 1] - a[op]).len()));
    }
    return ans;
}
// 平面最近点对部分
template<class T>
static bool cmpx(Point<T> &a, Point<T> &b) {
	return a.x < b.x || (a.x == b.x && a.y < b.y);
}
template<class T>
static bool cmpy(Point<T> &a, Point<T> &b) {
    return a.y < b.y || (a.y == b.y && a.x < b.x);
}
template<class T> //平面最近点对 必须先对p使用上面的cmp排序后使用 l r为p下标范围
T Closest_Pair(vector<Point<T>> p,int left, int right) {
    Point<T> tmpt[maxp];
    T d = inf;
    if (left == right) return d;
    if (left + 1 == right) return distance(p[left],p[right]);
    int mid = (left + right) / 2;
    T d1 = Closest_Pair(p,left, mid);
    T d2 = Closest_Pair(p,mid + 1, right);
    d = min(d1, d2);
    int cnt = 0;
    for (int i = left; i <= right; i++) {
        if (fabs(p[mid].x - p[i].x) <= d)
            tmpt[cnt++] = p[i];
    }
    sort(tmpt, tmpt + cnt, cmpy);
    for (int i = 0; i < cnt; i++) {
        for (int j = i + 1; j < cnt && tmpt[j].y - tmpt[i].y < d; j++)
            d = min(d, distance(tmpt[i],tmpt[j]));
    }
    return d;
}
Point<double> O(0,0);
void solve(){
    int n,k;
    cin>>n>>k;
    vector<Point<double>> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end(),ACcmp(O));
    if(k==n){
        cout<<setprecision(10)<<fixed<<2.0*pi<<"\n";
        return;
    }
    double mx=0;
    for(int i=0;i<n;i++){
        int x=i;
        int y=(i+k-1)%n;
        if(y>=x) mx=max(mx,rad(a[y])-rad(a[x]));
        else mx=max(mx,rad(a[y])-rad(a[x])+pi);
        
    }
    cout<<fixed<<setprecision(10)<<mx<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}