Symmetrical Patterns
In areas where alien spacecraft might land, symmetrical patterns known as "crop circles" are sometimes discovered. Occasionally, pranksters create fake patterns. However, humans cannot replicate the perfect symmetry of genuine "crop circles," making it possible to identify fakes. Recently, two patterns were observed in a field. To verify their authenticity, these patterns were photographed. A line was drawn through the centers of the patterns, and points belonging to the patterns were marked on this line. It is not exactly known which points belong to which pattern, but it is certain that all points of one pattern lie on one side of all points of the other pattern on the drawn line.
Write a program to determine whether the set of marked points can be divided into two non-empty subsets, each symmetrical, with one subset lying strictly to the left of the other.
Input
The first line of the input specifies the number of tests T, which is either 1 or 2. Each test is described on a separate line. At the beginning of each line is an integer N (1 ≤ N ≤ 100000) — the number of points on the line for the given test. Following this are N distinct integers x_1, x_2, ..., x_N — the coordinates of the points on the line.
It is known that 0 ≤ x_1 < x_2 < ... < x_N ≤ 2·10^9. The numbers in the line are separated by spaces.
Output
For each of the T tests, output the answer on a separate line. If, for the given test, the set of points can be divided into two non-empty symmetrical sets such that all points of one set lie on one side of all points of the other, output the number of points in the set with smaller coordinates. If multiple answers are possible, output the smallest natural number possible. If no such division exists, output 0.