There is a convex polygon with $$$n$$$ vertices. Vertices are numbered from $$$1$$$ to $$$n$$$ (both inclusive) in counter-clockwise order, and vertex $$$i$$$ has a value of $$$f(i)$$$.
We say a subset of the vertices is palindromic, if their values constitute a palindrome in counter-clockwise order. More formally, let's say the subset contains $$$k$$$ vertices $$$v_0, v_1, \cdots, v_{k - 1}$$$ in counter-clockwise order. There should exist an integer $$$d$$$ such that $$$0 \le d \lt k$$$, and for all $$$0 \le i \lt k$$$ we have $$$f(v_{(d + i) \bmod k}) = f(v_{(d - 1 - i) \bmod k})$$$.
Among all palindromic subsets, find the one whose convex hull has the largest size.
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 500$$$) indicating the number of vertices of the convex polygon.
The second line contains $$$n$$$ integers $$$f(1), f(2), \cdots, f(n)$$$ ($$$1 \le f(i) \le 10^9$$$) where $$$f(i)$$$ is the value of the $$$i$$$-th vertex.
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 coordinates of the $$$i$$$-th vertex. The vertices are listed in counter-clockwise order. The convex polygon is guaranteed to have positive size and no two vertices coincide. However there might be three vertices lying on the same line.
It's guaranteed that the sum of $$$n$$$ of all test cases does not exceed $$$10^3$$$.
For each test case output one line containing one integer, indicating the size of the largest convex hull of a palindromic subset, multiplied by $$$2$$$. It can be proven that this value is always an integer.
382 4 2 4 3 4 5 32 30 6-3 3-3 0-2 -31 -53 -34 031 2 30 01 00 131 1 10 01 00 1
84 0 1
The first sample test case is illustrated below. Choose vertices $$$2$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$8$$$ and consider $$$d = 1$$$, then the value sequence $$$\{4, 3, 4, 3, 4\}$$$ is a palindrome.
