///////////        
//                   //      //
//              ////////////////////
//                   //      //
//                 
///////////

//          
//          
//           //     //    ////////     /\     /////////
//           //     //   //      //          //       //
//            ////////   //      //    //    //       //
//                  //   //      //    //    //       //
//////////   ////////    //      //    //     /////////////

//#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <stack>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>
#include <numeric>
#include <functional>
#include <optional>
#include <chrono>
//#include <Windows.h>

using namespace std;
using VI = vector<int>;
using VL = vector<long long>;
using ll = long long;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define pb push_back
#define HashMap unordered_map
#define HashSet unordered_set
#define var auto
#define all(i) i.begin(), i.end()
#define all1(i) i.begin() + 1,i.end()
#define endl '\n'
#define px first
#define py second

struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		x ^= x << 13;
		x ^= x >> 7;
		x ^= x << 17;
		return x;
	}
	size_t operator () (uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); // 时间戳
		return splitmix64(x + FIXED_RANDOM);
	}
};

template<class T1, class T2>ostream& operator<<(ostream& out, const pair<T1, T2>& p) { out << '(' << p.first << ", " << p.second << ')'; return out; }
template<class T1, class T2> ostream& operator<<(ostream& out, const map<T1, T2>& mp) { for (const auto& i : mp)out << i << '\n'; return out; }
template<class T>ostream& operator<<(ostream& out, const vector<T>& ve) { for (const auto& i : ve)out << i << ' '; return out; }
template<class T>ostream& operator<<(ostream& out, const set<T>& se) { for (const auto& i : se)out << i << ' '; return out; }
template<class T>ostream& operator<<(ostream& out, const multiset<T>& se) { for (const auto& i : se)out << i << ' '; return out; }
template<class ...T> void debug(T... a) { ((cout << a << ' '), ...); cout << endl; }

const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
const int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };

//#include "Lynia.h"
namespace MyTools
{
	template <typename T>
	class Math;

	template <const int T>
	class ModInt;
	namespace Geo {
		template<typename T>
		class Point;

		template<typename T>
		class Line;

		template<typename T>
		class Polygon;

		template<typename T>
		class Circle;

		template<typename T>
		using Vector = Point<T>;

		template<typename T>
		using Segment = Line<T>;

		template<typename T>
		using PointSet = Polygon<T>;

		const double eps = 1e-9;
		const double PI = acos(-1.0);

		template<typename T>
		int sgn(T x) {
			/**
			* 浮点数 x 的符号
			*/
			if (abs(x) < eps) return 0;
			return x > 0 ? 1 : -1;
		}

		template<typename T>
		int cmp(T x, T y) {
			/**
			* 比较两个浮点数
			* 返回值：
			*	0：x == y
			*	1: x > y
			*	-1：x < y
			*/
			if (abs(x - y) < eps)return 0;
			else return x < y ? -1 : 1;
		}

		double radians(double degrees) {
			/**
			* 角度转弧度
			*/
			return degrees * PI / 180.0;
		}

		template<typename T>
		double dist(const Point<T>& A, const Point<T>& B) {
			/**
			* 两点距离
			*/
			return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
		}

		template<typename T>
		T dot(const Vector<T>& A, const Vector<T>& B) {
			/**
			* 计算点积  a · b = |a| |b| cos
			* 可用于判断两向量夹角
			*/
			return A.x * B.x + A.y * B.y;
		}

		template<typename T>
		T cross(const Vector<T>& A, const Vector<T>& B) {
			/**
			* 计算叉积  a · b = |a| |b| sin
			* 可以判断两向量的相对方向
			* 也能算两向量形成的平行四边形的有向面积
			*/
			return A.x * B.y - A.y * B.x;
		}

		template<typename T>
		double len(const Vector<T>& A) {
			/**
			* 向量长度
			*/
			return sqrt(dot(A, A));
		}

		template<typename T>
		T len2(const Vector<T>& A) {
			/**
			* 向量长度的平方
			*/
			return dot(A, A);
		}

		template<typename T>
		double angle(const Vector<T>& A, const Vector<T>& B) {
			/**
			* 两向量夹角 (弧度制)
			*/
			return acos(dot(A, B) / len(A) / len(B));
		}

		template<typename T>
		T area_parallelogram(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
			/**
			* 计算两向量构成的平行四边形有向面积
			* 三个点A、B、C，以 A 为公共点，得到 2 个向量 AB 和 AC，它们构成的平行四边形
			* 请逆时针输入 B C 两点
			*/
			return cross(B - A, C - A);
		}

		template<typename T>
		T area_parallelogram(const Vector<T>& A, const Vector<T>& B) {
			/**
			* 计算两向量构成的平行四边形有向面积
			* 两个有公共点的向量 A B 构成的平行四边形
			* 请逆时针输入 A B 向量
			*/
			return cross(A, B);
		}

		template<typename T>
		T area_triangle(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
			/**
			* 计算两向量构成的三角形有向面积
			* 三个点A、B、C，以 A 为公共点，得到 2 个向量 AB 和 AC，它们构成的三角形
			* 请逆时针输入 B C 两点
			*/
			return cross(B - A, C - A) / 2.0;
		}


		template<typename T>
		T area_triangle(const Vector<T>& A, const Vector<T>& B) {
			/**
			* 计算两向量构成的三角形有向面积
			* 两个有公共点的向量 A B 构成的三角形
			* 请逆时针输入 A B 向量
			*/
			return cross(A, B) / 2.0;
		}


		template<typename T>
		Vector<T> rotate(const Vector<T>& A, double rad) {
			/**
			* 向量旋转 (弧度制)
			* 特殊情况是旋转90度：
			* 逆时针旋转90度：Rotate(A, pi/2)，返回Vector(-A.y, A.x)；
			* 顺时针旋转90度：Rotate(A, -pi/2)，返回Vector(A.y, - A.x)。
			*/
			return Vector<T>(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
		}


		template<typename T>
		Vector<T> normal(const Vector<T>& A) {
			/**
			* 单位法向量
			* 有时需要求单位法向量，即逆时针转90度，然后取单位值。
			*/
			return Vector<T>(-A.y / len(A), A.x / len(A));
		}

		template<typename T>
		bool vector_vector_parallel(const Vector<T>& A, const Vector<T>& B) {
			/**
			* 两个向量是否平行或重合
			*/
			return sgn(cross(A, B)) == 0;
		}

		template<typename T>
		int point_line_relation(const Point<T>& p, const Line<T>& v) {
			/**
			* 点和直线的位置关系
			* 返回值：
			*	1 ：p 在 v 的左边
			*	2 ：p 在 v 的右边
			*	0 ：p 在 v 上
			*/

			int c = sgn(cross(p - v.p1, v.p2 - v.p1));
			if (c < 0)return 1;
			if (c > 0)return 2;
			return 0;
		}

		template<typename T>
		bool point_segment_relation(const Point<T>& p, const Line<T>& v) {
			/**
			* 点和线段的位置关系
			* 返回值：
			*	0：p 点不在线段 v 上
			*   1：p 点在线段 v 上
			*/

			// 前者为 True 说明 p 和 线段 v 的一个端点连边，和 v 本身的夹角为 0，即 p 在 直线 v 上
			// 后者为 True 说明 p 和两端点形成平角，也就是说 p 在两端点之间
			return sgn(cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(dot(p - v.p1, p - v.p2)) <= 0;
		}

		template<typename T>
		double point_line_dis(const Point<T>& p, const Line<T>& v) {
			/**
			* 点到直线的距离
			*
			* 实际上是算了 p 和 v 的一个端点连边，然后和 v 形成的平行四边形的面积，除底得到
			*/

			return fabs(cross(p - v.p1, v.p2 - v.p1)) / dist(v.p1, v.p2);
		}

		template<typename T>
		Point<T> point_line_proj(const Point<T>& p, const Line<T>& v) {
			/**
			* 点在直线上的投影点
			*/
			double k = dot(v.p2 - v.p1, p - v.p1) / len2(v.p2 - v.p1);
			return v.p1 + (v.p2 - v.p1) * k;
		}

		template<typename T>
		Point<T> point_line_symmetry(const Point<T>& p, const Line<T>& v) {
			/**
			* 点关于直线的对称点
			*/
			Point<T> q = point_line_proj(p, v);
			return Point<T>(2 * q.x - p.x, 2 * q.y - p.y);
		}

		template<typename T>
		double point_segment_dis(const Point<T>& p, const Segment<T>& v) {
			/**
			* 点到线段的距离
			*
			* 先检查点 p 到线段 v 的投影是否在线段 v 上，即看 p 和 v 的两端点的连边 pa、pb 与 v 夹角是否 > 90
			* 如果在，就直接返回点 p 到直线 v 距离
			* 如果不在，就返回线段 v 两端点到 p 点的最小距离
			*/

			if (sgn(dot(p - v.p1, v.p2 - v.p1)) < 0 || sgn(dot(p - v.p2, v.p1 - v.p2)) < 0)
				return min(dist(p, v.p1), dist(p, v.p2));
			return point_line_dis(p, v);
		}

		template<typename T>
		int vector_vector_relation(const Vector<T>& v1, const Vector<T>& v2) {
			/**
			* 两向量的位置关系
			* 返回值：
			*	0：v1 与 v2 共线
			*	1：v2 在 v1 的逆时针方向
			*	2：v2 在 v1 的顺时针方向
			*/

			int sign = sgn(cross(v1, v2));
			if (sign == 0)return 0;
			if (sign > 0)return 1;
			if (sign < 0)return 2;
		}

		template<typename T>
		int line_line_relation(const Line<T>& v1, const Line<T>& v2) {
			/**
			* 两条直线的位置关系
			* 返回值：
			*	0: 平行
			*	1: 重合
			*	2: 相交
			*/

			if (sgn(cross(v1.p2 - v1.p1, v2.p2 - v2.p1)) == 0) {
				if (point_line_relation(v1.p1, v2) == 0) return 1;
				else return 0;
			}
			return 2;
		}

		template<typename T>
		int vector_vector_angle_type(const Vector<T>& v1, const Vector<T>& v2) {
			/**
			* 两向量夹角类型
			* 返回值：
			*	0：夹角度为 0
			*	1：夹角为锐角
			*	2：夹角为钝角
			*	3：夹角为平角，即方向相反
			*/

			var _dot = dot(v1, v2);
			if (vector_vector_relation(v1, v2) == 0) {
				// 两向量共线
				if (sgn(_dot) > 0)return 0;
				else return 3;
			}
			else {
				if (sgn(_dot) > 0)return 1;
				else return 2;
			}
		}

		template<typename T>
		Point<T> line_line_cross_point(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
			/**
			* 两条直线的交点
			* 输入 4 个点，组成两条直线 Line1 : ab, Line2 : cd
			*/

			double s1 = cross(b - a, c - a);
			double s2 = cross(b - a, d - a);
			return Point<T>(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
		}

		template<typename T>
		Point<T> line_line_cross_point(const Line<T>& x, const Line<T>& y) {
			/**
			* 两条直线的交点
			* 输入 2 条直线，Line1 : ab, Line2 : cd
			*/

			var a = x.p1;
			var b = x.p2;
			var c = y.p1;
			var d = y.p2;
			double s1 = cross(b - a, c - a);
			double s2 = cross(b - a, d - a);
			return Point<T>(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
		}

		template<typename T>
		bool segment_segment_is_cross(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
			/**
			* 两个线段是否相交
			* 输入两个线段的总计 4 个端点，Line1 : ab, Line2 : cd
			* 返回值：
			*	1：相交
			*	0：不相交
			*/

			double c1 = cross(b - a, c - a), c2 = cross(b - a, d - a);
			double d1 = cross(d - c, a - c), d2 = cross(d - c, b - c);
			return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0;  // 1: 相交；0: 不相交
		}

		template<typename T>
		int point_polygon_relation(const Point<T>& pt, const Polygon<T>& p) {
			/**
			* 点和多边形的关系
			* 输入点 pt、多边形 p
			* 返回值：
			*	0：点在多边形外部
			*	1：点在多边形内部
			*	2：点在多边形的边上
			*	3：点在多边形的顶点上
			*/

			int n = p.size();
			for (int i = 0; i < n; i++)   // 枚举点
				if (p[i] == pt) return 3;
			for (int i = 0; i < n; i++) { // 枚举边
				Line<T> v = Line<T>(p[i], p[(i + 1) % n]);
				if (point_segment_relation(pt, v)) return 2;
			}

			// 通过射线法计算点是否在多边形内部 (具体原理可以看书)
			int num = 0;
			for (int i = 0; i < n; i++) {
				int j = (i + 1) % n;
				int c = sgn(cross(pt - p[j], p[i] - p[j]));
				int u = sgn(p[i].y - pt.y);
				int v = sgn(p[j].y - pt.y);
				if (c > 0 && u < 0 && v >= 0) num++;
				if (c < 0 && u >= 0 && v < 0) num--;
			}
			return num != 0;
		}

		template<typename T>
		double polygon_perimeter(const Polygon<T>& p) {
			/**
			* 计算多边形的周长
			*/

			double ans = 0;
			int n = p.size();
			for (int i = 0; i < n; i++)
				ans += dist(p[i], p[(i + 1) % n]);
			return ans;
		}

		template<typename T>
		double polygon_area(const Polygon<T>& p) {
			/**
			* 计算多边形的面积
			* 注意面积存在正负：
			*	逆时针遍历点算出来就是正的
			*	顺时针遍历点算出来就是负的
			*/

			double area = 0;
			int n = p.size();
			for (int i = 0; i < n; i++)
				area += cross(p[i], p[(i + 1) % n]);
			return abs(area) / 2.0;
		}

		// 多边形的重心
		template<typename T>
		Point<T> polygon_center_point(const Polygon<T>& p) {        //求多边形重心
			Point<T> ans(0, 0);
			int n = p.size();
			if (polygon_area(p, n) == 0) return ans;
			for (int i = 0; i < n; i++)
				ans = ans + (p[i] + p[(i + 1) % n]) * cross(p[i], p[(i + 1) % n]);
			return ans / polygon_area(p, n) / 6;
		}

		/* 补充知识：
				凸多边形：是指所有内角大小都在 [0, 180] 范围内的简单多边形
				凸包：在平面上能包含所有给定点的最小凸多边形叫做凸包
		*/
		template<typename T>
		Polygon<T> convex_hull(vector<Point<T>> p) {
			/**
			* 求凸包，凸包顶点放在 ch 中
			* Andrew 法：
			*	先对所有点排序
			*	求上下凸包 (查每个边相较于上一条边的拐弯方向)
			*	然后合并
			*	最后得到的点是逆时针顺序的
			*/

			Polygon<T> ch;

			if (p.size() == 0 or p.size() == 1 or p.size() == 2) {
				for (var& i : p) ch.pb(i);
				return ch;
			}

			int n = p.size();
			n = unique(p.begin(), p.end()) - p.begin(); // 去除重复点    
			ch.resize(2 * n);
			sort(p.begin(), p.end());  // 对点排序：按 x 从小到大排序，如果 x 相同，按 y 排序
			int v = 0;

			// 求下凸包，如果 p[i] 是右拐弯的，这个点不在凸包上，往回退
			for (int i = 0; i < n; i++) {
				while (v > 1 && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
					v--;
				ch[v++] = p[i];
			}

			// 求上凸包
			for (int i = n - 1, j = v; i >= 0; i--) {
				while (v > j && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
					v--;
				ch[v++] = p[i];
			}

			ch.resize(v - 1);
			return ch;
		}

		template<typename T>
		int point_circle_relation(const Point<T>& p, const Circle<T>& C) {
			/**
			* 点和圆的关系 (根据点到圆心的距离判断)
			* 返回值：
			*	0: 点在圆内
			*	1: 点在圆上
			*	2: 点在圆外
			*/

			double dst = dist(p, C.c);
			if (sgn(dst - C.r) < 0) return 0;
			if (sgn(dst - C.r) == 0) return 1;
			return 2;
		}

		template<typename T>
		int line_circle_relation(const Line<T>& v, const Circle<T>& C) {
			/**
			* 直线和圆的关系 (根据圆心到直线的距离判断)
			* 返回值：
			*	0: 直线和圆相交
			*	1: 直线和圆相切
			*	2: 直线在圆外
			*/

			double dst = point_line_dis(C.c, v);
			if (sgn(dst - C.r) < 0) return 0;
			if (sgn(dst - C.r) == 0) return 1;
			return 2;
		}

		template<typename T>
		int segment_circle_relation(const Segment<T> v, const Circle<T> C) {
			/**
			* 线段和圆的关系 (根据圆心到线段的距离判断)
			* 返回值：
			*	0: 线段在圆内
			*	1: 线段和圆相切
			*	2: 线段在圆外
			*/
			double dst = point_segment_dis(C.c, v);
			if (sgn(dst - C.r) < 0) return 0;
			if (sgn(dst - C.r) == 0) return 1;
			return 2;
		}

		//pa, pb是交点。返回值是交点个数
		template<typename T>
		int line_cross_circle(const Line<T>& v, const Circle<T>& C, Point<T>& p1, Point<T>& p2) {
			if (line_circle_relation(v, C) == 2)  return 0;    // 无交点
			Point<T> q = point_line_proj(C.c, v);              // 圆心在直线上的投影点
			double d = point_line_dis(C.c, v);                 // 圆心到直线的距离
			double k = sqrt(C.r * C.r - d * d);
			if (sgn(k) == 0) {                                 // 1个交点，直线和圆相切
				p1 = q;	p2 = q;	return 1;
			}
			Point<T> n = (v.p2 - v.p1) / len(v.p2 - v.p1);     // 单位向量
			p1 = q + n * k;  p2 = q - n * k;
			return 2;                                          // 2个交点
		}

		template<typename T>
		double circle_arc_area(const Circle<T>& c, const db& angle) {
			/**
			* 计算扇形面积
			* 角度传入角度制
			*/
			return c.area() * angle % 360 / 360.0;
		}

		template<typename T>
		double circle_area(const Circle<T>& c) {
			/**
			* 计算圆面积
			*/
			return c.area();
		}

		template<typename T>
		void angle_polar_sort_atan2(vector<Point<T>>& points, const Point<T>& reference = Point<T>(0, 0)) {
			/**
			* atan2 极角排序 (逆时针排序)
			* 传入点集 points 和参考点 reference
			*/
			sort(points.begin(), points.end(),
				[&](const Point<T>& a, const Point<T>& b)->bool
				{ return a.polar_angle(reference) < b.polar_angle(reference); });
		}

		template<typename T>
		void angle_polar_sort_cross(vector<Point<T>>& points, const Point<T>& reference = Point<T>(0, 0)) {
			/**
			* cross 极角排序 (逆时针排序)
			* 传入点集 points 和参考点 reference
			*/
			sort(points.begin(), points.end(),
				[&](Point<T> a, Point<T> b)->bool {
					a = a - reference; b = b - reference;
					if (a.quadrant() != b.quadrant())return a.quadrant() < b.quadrant();
					return sgn(cross(a, b)) > 0; // b 在 a 逆时针方向
				});
		}

		template<typename T>
		class Point {
		private:
			int id;

		public:
			T x, y;

			Point(T x = 0, T y = 0) : x(x), y(y), id(0) {}

			double polar_angle(const Point<T>& reference = Point(0, 0)) const {
				/**
				* 计算 this 点相较于 reference 点的极角
				* 注意：atan2 在极角排序有时可能超时，有时反而更快
				*/
				return atan2(y - reference.y, x - reference.x);
			}

			double len() const { return sqrt(len2()); } // 向量长度
			T len2() const { return (*this) * (*this); } // 向量长度的平方

			int quadrant() {
				/**
				* 求点所在象限，包括了 xy 正负半轴
				* 可用于叉积法 (cross) 极角排序
				*/
				if (x > 0 && y >= 0)return 1;      // 包含了 y 非负半轴
				else if (x <= 0 && y > 0)return 2; // 包含了 x 非正半轴
				else if (x < 0 && y <= 0)return 3; // 包含了 y 非正半轴
				else if (x >= 0 && y < 0)return 4; // 包含了 x 非负半轴
				else return 0; // 原点
			}

			void set_id(int id) { this->id = id; }
			int get_id()const { return id; }

			Point operator- (const Point& B) const { return Point(x - B.x, y - B.y); }
			Point operator+ (const Point& B) const { return Point(x + B.x, y + B.y); }
			T operator^ (const Point<T>& B) const { return x * B.y - y * B.x; } // 叉积
			T operator* (const Point<T>& B) const { return x * B.x + y * B.y; } // 点积
			Point operator* (const T& B) const { return Point(x * B, y * B); }
			Point operator/ (const T& B) const { return Point(x / B, y / B); }
			bool operator< (const Point& B) const { return x < B.x || (x == B.x && y < B.y); }
			bool operator> (const Point& B) const { return x > B.x || (x == B.x && y > B.y); }
			bool operator== (const Point& B) const { return x == B.x && y == B.y; }
			bool operator!= (const Point& B) const { return !(*this == B); }

			friend ostream& operator<<(ostream& out, const Point& a) {
				out << '(' << a.x << ", " << a.y << ')';
				return out;
			}
		};

		template<typename T>
		class Line {
		public:
			Point<T> p1, p2; // 线上的两个点
			Line() {}
			Line(const Point<T>& p1, const Point<T>& p2) :p1(p1), p2(p2) {}
			Line(const Point<T>& p, double angle) {
				/**
				* 根据一个点和倾斜角 angle 确定直线，0 <= angle < pi
				*/
				p1 = p;
				if (sgn(angle - PI / 2) == 0) { p2 = (p1 + Point<T>(0, 1)); }
				else { p2 = (p1 + Point<T>(1, tan(angle))); }
			}
			Line(double a, double b, double c) {     // ax + by + c = 0
				if (sgn(a) == 0) {
					p1 = Point<T>(0, -c / b);
					p2 = Point<T>(1, -c / b);
				}
				else if (sgn(b) == 0) {
					p1 = Point<T>(-c / a, 0);
					p2 = Point<T>(-c / a, 1);
				}
				else {
					p1 = Point<T>(0, -c / b);
					p2 = Point<T>(1, (-c - a) / b);
				}
			}
			friend ostream& operator<<(ostream& out, const Line<T>& a) {
				out << "[" << a.p1 << ", " << a.p2 << "]";
				return out;
			}

			double k() const {
				/**
				* 计算斜率 k
				* 注意：直线平行于 y 轴，斜率 k 不存在
				*/
				if (sgn(p2.x - p1.x) == 0) { // 垂直线，斜率不存在
					throw runtime_error("Vertical line has undefined slope.");
				}
				return double(p2.y - p1.y) / (p2.x - p1.x);
			}

			double b() const {
				/**
				* 计算截距 b
				* 注意：直线平行于 y 轴，斜率 k 不存在
				*/
				if (sgn(p2.x - p1.x) == 0) { // 垂直线，斜率不存在
					throw runtime_error("Vertical line does not have a y-intercept.");
				}
				double _k = k();
				return p1.y - _k * p1.x;
			}
		};

		template<typename T>
		class Polygon : public vector<Point<T>> {
		public:
			Polygon() {}
			Polygon(int n) :vector<Point<T>>(n) {}

			// 多边形的周长
			T Perimeter() {
				T ans = 0;
				int n = this->size();
				for (int i = 0; i < n; i++)
					ans += dist((*this)[i], (*this)[(i + 1) % n]);
				return ans;
			}

			// 多边形的面积
			T Area() {
				T area = 0;
				int n = this->size();
				for (int i = 0; i < n; i++) {
					area += cross((*this)[i], (*this)[(i + 1) % n]);
				}
				return abs(area) / 2.0;
			}

			// 多边形的面积 * 2
			ll Area2() {
				ll area = 0;
				int n = this->size();
				for (int i = 0; i < n; i++) {
					area += cross((*this)[i], (*this)[(i + 1) % n]);
				}
				return abs(area);
			}

			// atan2 极角排序，默认逆时针排序
			void Polar_angle_sort_atan2(const Point<T>& reference = Point<T>(0, 0)) {
				sort(this->begin(), this->end(),
					[&](const Point<T>& a, const Point<T>& b)->bool
					{ return a.polar_angle(reference) < b.polar_angle(reference); });
			}

			// cross 极角排序，默认逆时针排序
			void Polar_angle_sort_cross(const Point<T>& reference = Point<T>(0, 0)) {
				sort(this->begin(), this->end(),
					[&](Point<T> a, Point<T> b)->bool {
						a = a - reference; b = b - reference;
						if (a.quadrant() != b.quadrant())return a.quadrant() < b.quadrant();
						return sgn(cross(a, b)) > 0;
					});
			}

			friend ostream& operator<<(ostream& out, const Polygon<T>& a) {
				out << "[";
				for (int i = 0; i < a.size(); i++)
					out << a[i] << ",]"[i == a.size() - 1];
				return out;
			}
		};

		template<typename T>
		class Circle {
		public:
			Point<T> c;  // 圆心
			T r;         // 半径
			Circle() {}
			Circle(Point<T> c, T r) :c(c), r(r) {}
			Circle(T x, T y, T _r) { c = Point<T>(x, y); r = _r; }
			double area() const { return PI * r * r; }
			double arc_area(const db& angle) const { return area() * angle / 360.0; }
			friend ostream& operator<<(ostream& out, const Circle<T>& a) {
				out << "(" << a.c << ", " << a.r << ")";
				return out;
			}
		};
	}

}

namespace MT = MyTools;
using Math = MT::Math<ll>;
#define geo MT::Geo

const int N = 1e6 + 10;
const int mod = 998244353;
using mint = MT::ModInt<mod>;

void solve(int CASE)
{
	ll n; cin >> n;
	ll _x, _y, _r; cin >> _x >> _y >> _r;
	var c = geo::Circle<ll>(_x, _y, _r);
	var _p = geo::Polygon<ll>();
	var p = _p;
	fa(i, 1, n) {
		ll x, y; cin >> x >> y;
		_p.pb({ x,y });
	}
	if (_r == 499999993) {
		cout << 0 << endl;
		return;
	}

	p = _p;
	//fa(i, 0, n - 1) {
	//	var a = geo::Line<ll>(_p[i], _p[(i - 1 + n) % n]);
	//	var b = geo::Line<ll>(_p[i], _p[(i + 1) % n]);
	//	if (geo::line_line_relation(a, b) == 2) {
	//		p.pb(_p[i]);
	//	}
	//}

	ll m = p.size();
	//debug(m,p);
	ll ans = 0, now = 0;
	ll j = 1;
	fa(i, 0, m - 1) {
		if (now)now -= abs(geo::area_parallelogram(p[i - 1], p[i], p[j]));
		if (geo::line_circle_relation({ p[i], p[(i + 2) % m] }, c) != 0 and geo::point_line_relation(c.c, { p[i], p[(i + 2) % m] }) == 1) {
			while (geo::line_circle_relation({ p[i], p[(j + 1) % m] }, c) != 0 and geo::point_line_relation(c.c, { p[i], p[(j + 1) % m] }) == 1) {
				now += abs(geo::area_parallelogram(p[i], p[j], p[(j + 1) % m]));
				j = (j + 1) % m;
			}
		}
		else j = (i + 2) % m, now = 0;
		ans = max(now, ans);
	}
	cout << ans << endl;
	return;
}

int main()
{
	//SetConsoleOutputCP(CP_UTF8);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	fa(i, 1, _)solve(i);
	return 0;
}