Under construction

Still being built. Things may change

Evenly Spaced Triples

Interview

Time limit1sMemory limit256 MB

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

Medium4 of 10

Topics
Hash map, Array
Solved
No attempts yet

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 Xb−Xa=Xc−XbX_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 Xb−Xa=3X_b - X_a = 3 and Xc−Xb=1X_c - X_b = 1, so the spacing is not equal. Taking -4, -1, 2 gives Xb−Xa=3X_b - X_a = 3 and Xc−Xb=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 (3≤N≤10003 \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.

Examples3

  1. Example 1

    Input
    2
    5
    2 0 -4 -1 4
    5
    1 3 2 5 4
    
    Expected output
    3
    4
    
  2. Example 2

    Input
    1
    3
    0 1 3
    
    Expected output
    0
    
  3. Example 3

    Input
    1
    3
    -100000000 0 100000000
    
    Expected output
    1