Evenly Spaced Triples

Given N distinct positions on a line, count how many triples of points have the middle point exactly halfway between the other two.

Medium4Hash mapArrayInterviewNo attempts yetTime limit1sMemory limit256 MB

Problem

There are NN distinct points marked on a line. Point ii sits at position XiX_i.

Pick three of the NN points and call the leftmost one aa, the middle one bb, and the rightmost one cc, at positions XaX_a, XbX_b, and XcX_c. The three points are evenly spaced when the distance between aa and bb equals the distance between bb and cc, that is, when XbXa=XcXbX_b - X_a = X_c - X_b.

Here is an example with N=5N = 5.

The points sit at -4, -1, 0, 2, and 4. Taking -4, -1, 0 as aa, bb, cc gives XbXa=3X_b - X_a = 3 and XcXb=1X_c - X_b = 1, so the spacing is not equal. Taking -4, -1, 2 gives XbXa=3X_b - X_a = 3 and XcXb=3X_c - X_b = 3, so those three points are evenly spaced. In this example the evenly spaced triples are (-4, -1, 2), (-4, 0, 4), and (0, 2, 4), so there are 3 of them.

Given the positions of the NN points, write a program that counts how many evenly spaced triples there are.

Input

The first line contains TT, the number of test cases. The TT test cases follow.

The first line of each test case contains the number of points NN (3N10003 \le N \le 1000). The second line contains the NN positions X1,X2,,XNX_1, X_2, \dots, X_N separated by spaces. Every position is an integer between -100,000,000 and 100,000,000, and all positions are distinct.

Output

For each test case, print the number of evenly spaced triples aa, bb, cc on its own line, in the order the test cases are given.