#include <bits/stdc++.h>
using namespace std;
typedef long double ldb;
#define int long long
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))  //若x>eps return 1 若x<-eps  return 2 否则返回0
const long double pi=acos(-1);
const int INF=0x3f3f3f3f;
const long double DINF=1e18,eps=1e-6;
typedef long long ll;
#define endl '\n'
struct Point
{
    long double x,y,z=0;
    Point(long double x=0,long double y=0):x(x),y(y){} //具体来说，这个构造函数带有两个参数 x 和 y，它们的默认值分别为 0。在这种情况下，如果您创建一个 Point 对象而没有提供任何参数，它将被初始化为 (0, 0)。
    long double abs() { return sqrt(abs2()); }
    long double abs2() { return x * x + y * y; }

};  
int sgn(long double x)
{
    if(fabs(x)<eps)
    {
        return 0;
    }
    if(x<0) return -1;
    return 1;
}
// !注意区分点和向量
typedef Point Vector;
// 向量平移之后还是那个向量，所以只需要原点和向量的终点即可
// !向量 + 向量 = 向量，点 + 向量 = 向量
Vector operator + (Vector A, Vector B){return Vector(A.x + B.x, A.y + B.y);}
// !点 - 点 = 向量(向量BC = C - B)
// 点+向量=向量
Vector operator - (Point A, Point B){return Vector(A.x - B.x, A.y - B.y);}
// !向量 * 数 = 向量
Vector operator * (Vector A, long double p){return Vector(A.x * p, A.y * p);}
// !向量 / 数= 向量
Vector operator / (Vector A, long double p){return Vector(A.x / p, A.y / p);}
// !点/向量的比较函数
bool operator < (const Point& a, const Point& b) {return sgn(a.x - b.x)<0 || (sgn(a.x - b.x)==0 & sgn(a.y - b.y)<0);}
// !求极角/ 在极坐标系中，平面上任何一点到极点的连线和极轴的夹角叫做极角。
// 单位弧度rad
long double Polar_angle(Vector A){return atan2(A.y, A.x);}
// !三态函数sgn用于判断相等，减少精度误差问题

bool cmpp(Point x,Point y,Point tttt)  
{
    return  (x-tttt).abs2()<(y-tttt).abs2();  //tttt是一个点，排序比较函数是x到tttt的欧几里得距离大小来比较
}
// 重载等于运算符
bool operator == (const Point& a, const Point& b){return !sgn(a.x - b.x) && !sgn(a.y - b.y);}
// !点积(满足交换律)
long double Dot(Vector A, Vector B){return A.x * B.x + A.y * B.y;}
// !向量的叉积(不满足交换律)
// 等于两向量有向面积的二倍(从v的方向看,w在左边,叉积>0,w在右边,叉积<0,共线,叉积=0)
// cross(x, y) = -cross(y, x)
// cross(x, y) : xAyB - xByA
long double Cross(Vector A, Vector B){return A.x * B.y - B.x * A.y;}  //二维叉积
long double dot_product(const Point &a, const Point &b) //三维点积
{
    return a.x * b.x + a.y * b.y + a.z * b.z;
}
Vector cross_product(Vector a, Vector b)  //三维叉积，返回的是向量
{
    Vector ans;
    ans.x = a.y * b.z - a.z * b.y;
    ans.y = a.z * b.x - a.x * b.z;
   ans.z = a.x * b.y - a.y * b.x;
    return ans;
}
bool ToLeftTest(Point a, Point b, Point c)  //判断向量bc是不是向量ab的逆时针方向，也可以看成一个点c是否在向量ab左边
{
    return Cross(b - a, c - b) > 0;
}
long double Length(Vector A){return sqrt(Dot(A, A));} //求向量模长
long double Angle(Vector A, Vector B){return acos(Dot(A, B) / Length(A) / Length(B));} //返回弧度制下的夹角
// !三个点确定两个向量,(交点为A的两个向量AB和AC)然后求这两个向量的叉积(叉乘)
long double Area2(Point A, Point B, Point C){return Cross(B - A, C - A);}
// !向量的单位法线实际上就是将该向量向左旋转90°
// 因为是单位法线所以长度归一化调用前请确保A不是零向量
Vector Normal(Vector A) //Normal表示逆时针90度的单位法向量
{
    long double L = Length(A);
    return Vector(-A.y / L, A.x / L);
}
inline Vector Format(const Vector &A) //归成单位向量
{
    long double L = Length(A);
    return Vector(A.x / L,A.y / L);
}
// !一个向量旋转rad弧度之后的新向量（点也行）
// !x' = xcosa - ysina, y' = xsina + ycosa
// rad:弧度 且为逆时针旋转的角
Vector Rotate(Vector A, long double rad)
{
    return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
inline Point turn_PP(Point a, Point b, long double theta)
{// 【将点A绕点B顺时针旋转theta(弧度)】  //注意是顺时针
    long double x = (a.x-b.x) * cos(theta) + (a.y-b.y) * sin(theta) + b.x;
    long double y = - (a.x-b.x) * sin(theta) + (a.y-b.y) * cos(theta) + b.y;
    return Point(x,y);
}
///线
struct Line
{// 直线定义
    Vector v;
    Point p;
    Line(Vector v, Point p):v(v), p(p) {}
    Point get_point_in_line(long double t)
    {// 返回直线上一点P = p + ( v)*t
        return p + (v)*t;
     }
};
//Line a(v,p);
// 点和直线关系
// 1 在左侧
// -1 在右侧
// 0 在直线上 / 直线上两点s和e
// A, B:直线上一点,C:待判断关系的点
int relation_point(Point A, Point B, Point C)
{
    // 1 left -1 right 0 in
    int c = sgn(Cross((B - A), (C - A)));
    if(c < 0) return 1;
    else if(c > 0) return -1;
    return 0;
}
long double xmult(Point p1,Point p2,Point p0)  //返回向量p0p1,p0p2的叉积
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
/// 调用前要确保两直线p + tv 和 Q + tw之间有唯一交点，当且仅当Corss(v, w) ! 0;（t是参数）
Point Get_line_intersection(Point P,Vector v,Point Q,Vector w)
{
    Vector u = P - Q;
    long  double t = (ldb)Cross(w, u) / (ldb)Cross(v, w);
    return P + v * t;
}
long double Dis_point_to_point(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
long double Dis_point_to_point2(Point a,Point b)
{
    return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
// !直线的参数式 直线 AB:A + tv(v为向量AB, t为参数)
long double Distance_point_to_line(Point P, Point A, Point B)  //P到ab直线的距离
{
    Vector v1 = B - A, v2 = P - A;
    return fabs(Cross(v1, v2) / Length(v1));// 如果不取绝对值，那么得到的是有向距离
}
// 垂线距离或者PA或者PB距离
long double Distance_point_to_segment(Point P, Point A, Point B)  //p到ab线段的距离
{
    if(A == B) return Length(P - A);// （如果重合那么就是两个点之间的距离，直接转成向量求距离即可）
    Vector v1 = B - A, v2 = P - A, v3 = P - B;
    if(sgn(Dot(v1, v2)) < 0) return Length(v2);// A点左边
    if(sgn(Dot(v1, v3)) > 0)return Length(v3);// B点右边
    return fabs(Cross(v1, v2) / Length(v1));// 垂线的距离
}
// !点在直线上的投影
// 点积满足分配率:两直线垂直，点积为0，向量v,Q = A + t0v,
// 点P,v与直线PQ垂直:  
// Dot(v, p - (A + t0v)) = 0 -> Dot(v, P - A) - t0 * Dot(v, v) = 0;
Point Get_line_projection(Point P, Point A, Point B) //求点p在ab直线上的投影点
{
    Vector v = B - A;
    return A + v * (Dot(v, P - A) / Dot(v, v));
}
inline Point FootPoint(Point p, Point a, Point b)  //投影点和垂足好像没有什么区别
{// 【点P到直线AB的垂足】
    Vector x = p - a, y = p - b, z = b - a;
    long double len1 = Dot(x, z) / Length(z), len2 = - 1.0 * Dot(y, z) / Length(z);// 分别计算AP,BP在AB,BA上的投影
    return a + z * (len1 / (len1 + len2));// 点A加上向量AF
}
inline Point Symmetry_PL(Point p, Point a, Point b)
{
    // 【点P关于直线AB的对称点】
    return p + (FootPoint(p, a, b) - p) * 2;
    // 实际上就是求垂足之后延长一倍得到的向量，与原来的点加起来就行了
}
bool OnSegment(Point p, Point a1, Point a2)  //点是否在线段上
{
    return sgn(Cross(a1-p, a2-p)) == 0 & sgn(Dot(a1-p, a2-p)) <= 0;
}
bool segment_proper_intersection(Point a1, Point a2, Point b1, Point b2) //线段是否相交 不含端点
{
    long double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1);
    long double c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
    return sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0;
    
}
bool Segment_proper_intersection(Point a1, Point a2, Point b1, Point b2)// 线段是否相交 包含端点相交
{

    long double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1);
    long double c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);
    // if判断控制是否允许线段在端点处相交，根据需要添加
    if(!sgn(c1) || !sgn(c2) || !sgn(c3) || !sgn(c4))
    {
        bool f1 = OnSegment(b1, a1, a2);
        bool f2 = OnSegment(b2, a1, a2);
        bool f3 = OnSegment(a1, b1, b2);
        bool f4 = OnSegment(a2, b1, b2);
        bool f = (f1|f2|f3|f4);
        return f;
    }
    return (sgn(c1)*sgn(c2) < 0 && sgn(c3)*sgn(c4) < 0);
}
bool on_segment(Point P, Point a1, Point a2)  //判断点是否在线段上（不含端点）
{
    return sgn(Cross(a1 - P, a2 - P)) == 0 & sgn(Dot(a1 - P, a2 - P)) < 0;
}
Point segment_intersection(Point p1,Point p2,Point p3,Point p4)  //默认有交点
{
    if(relation_point(p1,p2,p3)==0) return p3;
    else if(relation_point(p1,p2,p4)==0) return p4;
    else if(relation_point(p3,p4,p1)==0) return p1;
    else if(relation_point(p3,p4,p2)==0) return p2;
    long double t=Cross(p1-p3,p3-p4)/Cross(p1-p2,p3-p4);
    long double s=Cross(p1-p3,p1-p2)/Cross(p1-p2,p3-p4);
    Point ans;
    ans.x=p1.x+t*(p2.x-p1.x);  //x=p3.x+s*(p4.x-p3.x);
    ans.y=p1.y+t*(p2.y-p1.y);  //y=p3.y+s*(p4.y-p4.y);
    return ans;

}
long double Distance_segment_to_segment(Point p1,Point p2,Point p3, Point p4)
{
    if(Segment_proper_intersection(p1,p2,p3,p4)) return 0.00;
    long double ans=1e9;
    ans=min(ans,Distance_point_to_segment(p3,p1,p2));
    ans=min(ans,Distance_point_to_segment(p4,p1,p2));
    ans=min(ans,Distance_point_to_segment(p1,p3,p4));
    ans=min(ans,Distance_point_to_segment(p2,p3,p4));
    return ans;
}
////多边形
//求多边形面积
long double polyg_on_area(vector<Point> cnt,int n)  //n边形
{
    long double area=0;
    for(int i=1;i<=n-2;i++)
    {
        area+=Cross(cnt[i]-cnt[0],cnt[i+1]-cnt[0]);
    }
    return area/2;

}
int is_point_in_polygon(Point p,vector<Point> poly)  //判断点是否在多边形内部，是返回1，不是返回0，在多边形上返回-1
{
    int wn=0;
    int n=poly.size();
    for(int i=0;i<n;i++)
    {
        if(OnSegment(p,poly[i],poly[(i+1)%n])) return -1;
        int k=sgn(Cross(poly[(i+1)%n]-poly[i],p-poly[i]));
        int d1=sgn(poly[i].y-p.y);
        int d2=sgn(poly[(i+1)%n].y-p.y);
        if(k>0&&d1<=0&&d2>0) wn++;
        if(k<0&&d2<=0&&d1>0) wn--;
    }
    if(wn!=0) return 1;
    return 0;
}
int is_convex(int n,vector<Point> p)  //判断是否为凸多边形，顶点按顺时针或者逆时针给出，允许邻边共线
{
    int s[3]={1,1,1};
    for(int i=0;i<n&&(s[1]|s[2]);i++)
    {
        s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
    }
    return s[1]|s[2];

}
int is_convex_v2(int n,vector<Point> p) //不允许邻边共线
{
    int s[3]={1,1,1};
    for(int i=0;i<n&&(s[1]|s[2])&&s[0];i++)
    {
        s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
    }
    return s[0]&&s[1]|s[2];
}
Point barycenter(int n,vector<Point> p)  //逆时针给点
{
    Point ans;
    ans.x=0;
    ans.y=0;
    long double ss=0;
    for(int i=1;i<n-1;i++)
    {
        if(fabs(xmult(p[i],p[i+1],p[0]))>eps)  //判断三点不共线
        {
            long double s=xmult(p[i],p[i+1],p[0]); //即使是非凸四边形，面积最后也会消掉，所以不用加绝对值
            ans.x+=(p[0].x+p[i].x+p[i+1].x)*s;
            ans.y+=(p[0].y+p[i].y+p[i+1].y)*s;
            ss+=s;
        }
    }
    if(fabs(ss)>eps)
    {
        ans.x/=ss;
        ans.x/=3;
        ans.y/=ss;
        ans.y/=3;
    }
    return ans;
}
int segment_isin_polygon(Point l1,Point l2,int n,vector<Point> p)//判断线段是否在多边形内（顶点在边上也算在多边形内）
{
    if(!is_point_in_polygon(l1,p)||!is_point_in_polygon(l2,p)) return 0;
    vector<Point> t;
    for(int i=0;i<n;i++)
    {
        if(segment_proper_intersection(l1,l2,p[i],p[(i+1)%n])) return 0;
        else if(OnSegment(l1,p[i],p[(i+1)%n])) t.push_back(l1);
        else if(OnSegment(l2,p[i],p[(i+1)%n])) t.push_back(l2);
        else if(OnSegment(p[i],l1,l2)) t.push_back(p[i]);
    }
    sort(t.begin(),t.end());  //或者暴力枚举每两个点
    for(int i=0;i<t.size()-1;i++)
    {
        Point tt;
        tt.x=(t[i].x+t[i+1].x)/2;
        tt.y=(t[i].y+t[i+1].y)/2;
        if(!is_point_in_polygon(tt,p)) return 0;
    }
    return 1;

}
struct Circle
{
    Point c;
    long double r;
    Circle(Point c=Point(),long double r=0):c(c),r(r){} //Circle c
     //若要访问圆心  c.c.x   c.c.y
    inline Point point(long double a) //通过圆心角求坐标
    {
        return Point(c.x+cos(a)*r,c.y+sin(a)*r);
    }
};

int get_line_circle_intersection(Line L,Circle C,long double &t1,long double &t2,vector<Point>& sol)
{
    long double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
    long double e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;
    long double delta1 = f*f - 4*e*g;// 判别式
    if(sgn(delta1) < 0)// 相离
    return 0;
    if(sgn(delta1) == 0){// 相切
    t1 = -f /(2*e);
    t2 = -f /(2*e);
    sol.push_back(L.get_point_in_line(t1));// sol存放交点本身
    return 1;
     }
      // 相交
    t1 = (-f - sqrt(delta1))/(2*e);
    sol.push_back(L.get_point_in_line(t1));
    t2 = (-f + sqrt(delta1))/(2*e);
    sol.push_back(L.get_point_in_line(t2));
    return 2;
}
int get_circle_circle_intersection(Circle c1,Circle c2,vector<Point> &sol)
{
    long double d = Length(c1.c - c2.c);
    if(sgn(d) == 0)
    {
        if(sgn(c1.r - c2.r) == 0)return -1;// 两圆重合
        return 0;
     }
    if(sgn(c1.r + c2.r - d) < 0)return 0;// 相离
    if(sgn(fabs(c1.r - c2.r) - d) > 0)return 0;// 在另一个圆的内部
    long double a = atan2((c2.c - c1.c).y,(c2.c-c1.c).x);// 向量c1c2的极角
    //cout<<a<<"dd"<<endl;
    long double da = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
    // c1c2到c1p1的角
    Point p1 = c1.point(a - da), p2 = c1.point(a + da);
    sol.push_back(p1);
    if(p1 == p2)return 1;
    sol.push_back(p2);
    return 2;
}
// 过点p到圆c的切线，v[i]是第i条切线， 返回切线的条数
int get_tangents(Point p, Circle C, vector<Vector> &k)
{
    Vector u = C.c - p;
    long double dist = Length(u);
    if(dist < C.r)return 0;// 点在内部，没有切线
    else if(sgn(dist - C.r) == 0)
    {// p在圆上，只有一条切线
        k.push_back(Rotate(u,pi/2));
        //v[0] = Rotate(u, pi / 2);// 切线就是垂直嘛
        return 1;
     }
    else 
    {// 否则是两条切线
        long double ang = asin(C.r / dist);
        k.push_back(Rotate(u,-ang));
        k.push_back(Rotate(u,+ang));
       // v[0] = Rotate(u, - ang);
       // v[1] = Rotate(u, +ang);
        return 2;
     }
}
int get_tangents_point(Point p,Circle c,vector<Point> &k)
{
    vector<Vector> ans;
    int cnt=get_tangents(p,c,ans);
    if(cnt==0) return 0;  //点在圆内
    if(cnt==1)
    {
        Line l(ans[0],p);
       long double t1,t2;
       int u=get_line_circle_intersection(l,c,t1,t2,k);
       // for(int i=0;i<=1;i++)
       // {
       //  std::cout << std::fixed << std::setprecision(8) <<kk[0].x<<' '<<kk[0].y<<endl;
       // }
       return 1;
    }
    else
    {
        Line l1(ans[0],p);
        Line l2(ans[1],p);
        vector<Point> kk;
        long double t1,t2;
        int u=get_line_circle_intersection(l1,c,t1,t2,k);
         u=get_line_circle_intersection(l2,c,t1,t2,k);
         sort(k.begin(),k.end());
         // for(int i=0;i<=1;i++)
         // {
         //    std::cout << std::fixed << std::setprecision(8) <<kk[i].x<<' '<<kk[i].y<<endl;
         // }
         return 2;
    }
}
inline Circle getcircle(Point A,Point B,Point C)  //求外接圆
{// 【三点确定一圆】向量垂直平分线法
    Point P1=(A+B)*0.5,P2=(A+C)*0.5;
    Point O=Get_line_intersection(P1,Normal(B-A),P2,Normal(C-A));
    return Circle(O,Length(A-O));
}
Circle NeiJieYuan(Point p1,Point p2,Point p3)  //求内接圆
{
   long double a=Length(p2-p3);
    long double b=Length(p3-p1);
    long double c=Length(p1-p2);
    Point p=(p1*a+p2*b+p3*c)/(a+b+c);
    return Circle(p,Distance_point_to_line(p,p1,p2));
}
Circle WaiJieYuan(Point p1,Point p2,Point p3)  //外接圆
{
    double Bx=p2.x-p1.x,By=p2.y-p1.y;
    double Cx=p3.x-p1.x,Cy=p3.y-p1.y;
    double D=2*(Bx*Cy-By*Cx);
    double ansx=(Cy*(Bx*Bx+By*By)-By*(Cx*Cx+Cy*Cy))/D+p1.x;
    double ansy=(Bx*(Cx*Cx+Cy*Cy)-Cx*(Bx*Bx+By*By))/D+p1.y;
    Point p(ansx,ansy);
    return Circle(p,Length(p1-p));
}
// 返回切线的条数，-1表示无穷条切线
// /a[i]和b[i] 分别是第i条切线在圆A和圆B上的切点
int get_circletangents(Circle A, Circle B, vector<Point> &a, vector<Point>&b)
{
    int cnt = 0;
    if(A.r < B.r)swap(A, B), swap(a, b);  //注意这里交换了，如果A.r<B.r  那么b里面存a的切点
    int d2 = (A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y);
    int rdiff = A.r - B.r;
    int rsum = A.r + B.r;
    if(d2 < rdiff * rdiff)return 0;// 内含
    double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
    if(d2 == 0 & A.r == B.r)return -1;// 无限多条切线
    if(d2 == rdiff * rdiff)
    {// 内切，1条切线
        a.push_back( A.point(base));
        b.push_back( B.point(base)); cnt ++ ;
        return 1;
     }
    // 有外共切线
    double ang = acos((A.r - B.r) / sqrt(d2));
    a.push_back( A.point(base + ang));b.push_back( B.point(base + ang));cnt ++ ;
    a.push_back(A.point(base - ang));b.push_back(B.point(base - ang));cnt ++ ;
    if(d2 == rsum * rsum)
    {   // 一条内公切线
        a.push_back(A.point(base));b.push_back(B.point(pi + base)); cnt ++ ;
     }
    else if(d2 > rsum * rsum)
    {   // 两条内公切线
        double ang = acos((A.r + B.r) / sqrt(d2));
        a.push_back(A.point(base + ang)); b.push_back(B.point(pi + base + ang)); cnt ++ ;
        a.push_back(A.point(base - ang)); b.push_back(B.point(pi + base - ang)); cnt ++ ;
    }
    return cnt;
}
//通过计算两个圆相交所构成的两个扇形面积和减去其构成的筝形的面积
long double AreaOfOverlap(Point c1, long double r1, Point c2, long double r2)  //求两圆相交面积
{
    long double d = Length(c1 - c2);
    //cout<<c2.x<<endl;
    if(r1 + r2 < d + eps)
    return 0.0;
    if(d < fabs(r1 - r2) + eps)
    {
        long double r = min(r1, r2);
        return pi*r*r;
     }
    long double x = (d*d + r1*r1 - r2*r2)/(2.0*d);
    long double p = (r1 + r2 + d)/2.0;
    long double t1 = acos(x/r1);
    long double t2 = acos((d - x)/r2);
    long double s1 = r1*r1*t1;
    long double s2 = r2*r2*t2;
    long double s3 = 2*sqrt(p*(p - r1)*(p - r2)*(p - d));
    return s1 + s2 - s3;
}
int grid_onedge(int n,vector<Point> p)  //返回多边形边上的网格点个数  s=in+(edge/2)-1  //面积s可以通过三角剖分叉积算
{
    int ret=0;
    for (int i=0;i<n;i++ )
    ret+=__gcd(abs((int)p[i].x-(int)p[(i+1)%n].x),abs((int)p[i].y-(int)p[(i+1)%n].y));
    return ret;
}
bool argcmp(const Point &a,const Point &b)  //下半平面<原点<x正半轴<上半平面<x负半轴
{
    auto quad=[](const Point &a)
    {
        if(a.y<-eps) return 1;  //在下半平面
        if(a.y>eps) return 4; //在上半平面
        if(a.x<-eps) return 5;//在负x轴
        if(a.x>eps) return 3;//在正x轴
        return 2;//在原点

    };
    int qa=quad(a),qb=quad(b);
    if(qa!=qb) return qa<qb;
    int t=(int)Cross(a,b);
    if(abs(t)<=eps) return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y-eps;  //如果t等0，说明他们的极角一样，这时候按照长度比
    return t>eps;

}
// 计算凸包，输入点数组p，个数为p输出点数组ch，函数返回凸包顶点个数。
// 输入不能有重复的点，函数执行完后的输入点的顺序将被破坏（因为要排序，可以加一个数组存原来的id）
// 如果不希望在凸包边上有输入点，把两个< 改成<=即可
int ConvexHull(vector<Point> &p, int n, vector<Point> &ch)
{
    sort(p.begin(), p.begin() + n);
    int m = 0;
    for(int i = 0; i < n; ++ i)
    {// 下凸包
    // 如果叉积<= 0说明新边斜率小说明已经不是凸包边了，赶紧踢走
        while(m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <=0)
        {
            m--;
            ch.pop_back();
        }
        ch.push_back(p[i]);
        m++;
     }
    int k = m;
    for(int i = n - 2; i >= 0; -- i)
    {// 上凸包
        while(m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <=0)
        {
            m--;
            ch.pop_back();
        }
        ch.push_back(p[i]);
        m++;
     }
    if(n > 1) m -- ;
    return m;
}
long double Convex_hull_diameter(vector<Point> p,int num) //返回直径平方，p必须没有三点共线的凸包
{
    if(num==2)
    {
        return (int)Dis_point_to_point2(p[0],p[1]);
        
    }
    if(num==3)
    {
        return max({(int)Dis_point_to_point2(p[0],p[1]),(int)Dis_point_to_point2(p[0],p[2]),(int)Dis_point_to_point2(p[1],p[2])});
    }
    p.push_back(p[0]);
    int pos=2;
    long double ans=-1e8;
    for(int i=0;i<p.size()-1;i++)
    {
        auto p1=p[i];
        auto p2=p[i+1];
        auto p3=p[pos];
        auto t=Area2(p1,p2,p3);
        long double maxx=t;
        int j=pos;
        while(j<p.size()-1&&Area2(p1,p2,p[j])>=maxx)
        {
            //j++;
            maxx=Area2(p1,p2,p[j]);
            ans=max({ans,Dis_point_to_point2(p1,p[j]),Dis_point_to_point2(p2,p[j])});
            j++;

        }
        pos=j-1;

    }
    return ans;

}
int is_in_convexhull(vector<Point> &p,Point t,int n) //n>=3,逆时针，要传数组指针
{
        if(t==p[0])
        {
            return 0;
        }
        if(OnSegment(t,p[0],p[1]))
        {
            return 0;
        }
        if(OnSegment(t,p[0],p[n-1]))
        {
            return 0;
        }
        if(ToLeftTest(p[0],p[n-1],t))
        {
            return 1;
        }
        if(ToLeftTest(p[1],p[0],t))
        {
            return 1;
        }
        int l=2,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(ToLeftTest(p[0],p[mid],t)) l=mid+1;
            else r=mid;
        }
        Point t1=p[l-1];
        Point t2=p[l];
        if(OnSegment(t,t1,t2))
        {
            return 0;
        }
        //cout<<t1.x<<"pa"<<t1.y<<endl;
        if(ToLeftTest(t1,t2,t))
        {
            return -1;
        }
        else return 1;
}
void solve()
{
    //  long double number = 3.14159265358979323846;
    
    // // 使用流操纵器保留6位小数并输出
    // std::cout << std::fixed << std::setprecision(6) << number << std::endl;
    
   // cout<<"aaa"<<endl;
    Circle c;
    int n;
    cin>>n;
    cin>>c.c.x>>c.c.y>>c.r;
    Point tt={c.c.x,c.c.y};  //圆心点
    vector<Point> p(2*n+1);  //存凸包
    for(int i=0;i<n;i++)
    {
        cin>>p[i].x>>p[i].y;
        p[i+n]=p[i];
    }
    if(n==3)
    {
        cout<<0<<endl;
        return ;
    }

    queue<int> q;
  //  long double t1=0,t2=0;
   // vector<Point> sol;
    int now=0;
    Point yuan={0,0};  //原点
    int ans=0;
    int j=0;
    //q.push(0);
    vector<bool> flag(2*n+10,0);
    while(1)
    {
        if(q.size()==0)
        {
            q.push(j);
            j++;
            j%=n;
            continue;
        }
            auto t=q.front();
            //if(flag[t]) break;
            Line line (p[j]-p[t],p[t]);
            
           // q.push(j);
            if(ToLeftTest(p[t],p[j],tt)&&sgn(Distance_point_to_line(tt,p[t],p[j])-c.r)==1)
            {
                q.push(j);
                now+=Cross(p[(j-1+n)%n]-yuan,p[j]-yuan);
                ans=max(ans,now+(int)Cross(p[j]-yuan,p[t]-yuan));
                
            }
            else
            {
                q.pop();
                if(flag[t]) break;
                flag[t]=1;
                if(q.size()!=0)
                now-=Cross(p[t]-yuan,p[(t+1)%n]-yuan);
                continue;
            }
            j++;
            j%=n;
    }
    cout<<ans<<endl;
    

   
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    //cout<<acos(-1.0)<<endl;
    while(T--)
    {
        solve();
    }
}