BaoBao has prepared a pizza for you! This pizza is a convex polygon with stuffed crust along all of its edges. However, the crust is delicate, allowing you to cut only through its vertices and not into the middle of the edges. Unfortunately, there's a sizable circular piece of pineapple on the pizza that you absolutely want to avoid.
Calculate the largest single piece of pineapple-free pizza that you can obtain with a single straight cut and output its size. A piece is considered pineapple-free when no part of the pineapple falls strictly within it. That is, the area of intersection of the pineapple and the pizza is $$$0$$$.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains an integer $$$n$$$ ($$$3 \le n \le 10^5$$$) indicating the number of vertices of the pizza.
The second line contains three integers $$$x_c$$$, $$$y_c$$$, and $$$r$$$ ($$$-10^9 \le x_c,y_c \le 10^9$$$, $$$1 \le r \le 10^9$$$), indicating the coordinates of the center of the pineapple and its radius.
For the following $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i,y_i \le 10^9$$$) indicating the coordinate of the $$$i$$$-th vertex. The vertices are listed in counter-clockwise order. No two points coincide. However there might be three points lying on the same line.
It is guaranteed that no part of the pineapple lies outside of the boundaries of the pizza. It's also guaranteed that the sum of $$$n$$$ of all the test cases does not exceed $$$10^5$$$.
For each test case, output one line containing one integer, indicating the size of the largest piece of pineapple-free pizza multiplied by $$$2$$$. It can be proven that this value will always be an integer. If there's no way to get a pineapple-free piece, output $$$0$$$.
351 1 10 01 05 03 30 562 4 12 04 06 34 62 60 343 3 13 06 33 60 3
5 24 0
The sample test cases are shown below.
