#include<bits/stdc++.h>
#include <algorithm>
#define mod 1000000007
#define ll long long
#define ull unsigned long long
#define f(i,a,n) for(ll i=a;i<n;i++)
#define vec vector<ll>
#define mxh priority_queue<pair<int,int>>
#define mh priority_queue<int,vector<int>,greater<int>>
#define omap map<ll,ll>
#define umap unordered_map<ll,ll>
#define vpair vector<pair<ll,ll> >
#define pb push_back
#define mp make_pair
#define sor(v) sort(v.begin(),v.end())
#define fi  first
#define se second
//#include <boost/math/common_factor.hpp>

using namespace std;
ll ipow(ll base, ll exp)
{
    ll result = 1;
    for (;;)
    {
        if (exp & 1)
            result= (result*base)%mod;
        exp >>= 1;
        if (!exp)
            break;
        base= (base*base)%mod;
    }

    return result;
}
bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}
ll fact(ll n)
{
    if (n >= mod)
        return 0;

    ll result = 1;
    for (int i = 1; i <= n; i++)
        result = (result * i) % mod;

    return result;
}
bool is_prime(ll n) {
    if (n == 1) {
        return false;
    }
    ll i = 2;
    while (i*i <= n) {
        if (n % i == 0) {
            return false;
        }
        i += 1;
    }
    return true;
}
bool areRotations(string str1, string str2)
{
   /* Check if sizes of two strings are same */
   if (str1.length() != str2.length())
        return false;

   string temp = str1 + str1;
  return (temp.find(str2) != string::npos);
}
bool pow2 (ll x)
{
    return x && (!(x&(x-1)));
}
ll maxXorSum(ll n, ll k)
{
    if (k == 1)
        return n;
    ll res = 1;
    while (res <= n)
        res <<= 1;

    // Return res - 1 which denotes
    // a number with all bits set to 1
    return res - 1;
}
ll mcost(ll a[], ll n)
{

    ll y;
    if (n % 2 == 1)
        y = a[n / 2];
    else
        y = (a[n / 2] + a[(n - 2) / 2]) / 2;

    ll s = 0;
    for(ll i = 0; i < n; i++)
        s += abs(a[i] - y);

    return s;
}
ll largest_subarray(ll a[], ll n)
{
    unordered_map<ll, ll> index;
    ll ans = 0;
    for (ll i = 0, j = 0; i < n; i++) {

        j = max(index[a[i]], j);
        ans = max(ans, i - j + 1);
        index[a[i]] = i + 1;
    }
    return ans;
}
ll b[101],sz;
pair<ll,ll> adj[101];

void dfs(int s)
{
    b[s]=1;
    for(int i=1;i<=sz;i++)
    {    if(!b[i] && (adj[s].first==adj[i].first || adj[s].second==adj[i].second))
            dfs(i);
    }
}
void display(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        cout << a[i] << "  ";
    }
    cout << endl;
}
void per(int a[], int n)
{  ll d=0;
    sort(a, a + n);
  //  cout << "Possible permutations are:\n";
    do { ll s=0,x=1;
        f(i,0,n)
        {
            s+=a[i];
            if(s==0)
            {
                x=-1;
            }
        }
        if(x==1)
        {    cout<<"YES"<<endl;
        d=1;
            f(i,0,n)
           {
             cout<<a[i]<<" ";
           }cout<<endl;
          break;
        }
    } while (next_permutation(a, a + n));
    if(d==0)
    {
        cout<<"NO"<<endl;
    }
}
int gcd(int a, int b)
{
    if (b == 0)
        return a;

    else
        return gcd(b, a % b);
}

bool leftRotate(int a[], int d, int n)
{

    d = d % n;
    int g_c_d = gcd(d, n);
    for (int i = 0; i < g_c_d; i++) {
        int temp = a[i];
        int j = i;

        while (1) {
            int k = j + d;
            if (k >= n)
                k = k - n;

            if (k == i)
                break;

            a[j] = a[k];
            j = k;
        }
        a[j] = temp;
    }
    ll s=0,x=1;
    f(i,0,n)
    {
        s+=a[i];
        if(s==0)
        {
            x=0;
        }
    }
    if(x==1)
    {   cout<<"YES"<<endl;
        f(i,0,n)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
      return true;
    }
    return false;

}
ll rec(ll n,ll k)
{
    if(n==1)
    {
        return 1;
    }
    if (k==1)
    {
        return n;
    }
    return ((n+rec(n-1,k-1))%mod);
}

bool isPerfectSquare(ll x)
{
  if(sqrt(x)*sqrt(x)==x)
  {
      return true;
  }
  return false;
}
bool isSubSequence(string str1,string str2, int m, int n)
{
   int j = 0,x=0,d=0;
    if(str1[0]==str2[0])
    {
        for (int i=0; i<n&&j<m; i++)
       {
           if (str1[j] == str2[i])
            {
              j++;

            }
           else
            {   d=i;
                break;
            }
       }
       if(j==m)
       {
           return true;
       }
       ll p=9,v=0;
       for(int i=n-1;i>=d;i--)
        {  //  cout<<"l";
            if(v==10-j)
            {
                break;
            }
            if(str1[p]==str2[i])
            {
                p--;
                v++;
            }

            else
            {
                break;
            }
        }
       //cout<<j<<" "<<v<<" "<<d<<endl;
        if(v+j==10)
        {
            return true;
        }
        else
        {
            return false;
        }


    }
    else{
         size_t found = str2.find(str1);
        if (found != string::npos && str1[9]==str2[n-1])
         {
             return true;
         }
         else
         {
             return false;
         }
    }

}
ll countBits(ll n)
{
   ll count = 0;
   while (n)
   {
        count++;
        n >>= 1;
    }
    return count;
}
void kFactors(int n, int k)
{
    // A vector to store all prime factors of n
    vector<int> P;

    // Insert all 2's in vector
    while (n%2 == 0)
    {
        P.push_back(2);
        n /= 2;
    }

    // n must be odd at this point
    // So we skip one element (i = i + 2)
    for (int i=3; i*i<=n; i=i+2)
    {
        while (n%i == 0)
        {
            n = n/i;
            P.push_back(i);
        }
    }

    // This is to handle when n > 2 and
    // n is prime
    if (n > 2)
        P.push_back(n);

    // If size(P) < k, k factors are not possible
    if (P.size() < k)
    {
        cout << "-1" << endl;
        return;
    }

    // printing first k-1 factors
    for (int i=0; i<k-1; i++)
        cout << P[i] << " ";

    // calculating and printing product of rest
    // of numbers
    int product = 1;
    for (int i=k-1; i<P.size(); i++)
        product = product*P[i];
    cout << product << endl;
}
ll fin(ll n)
{    ll x=0,y=0,z=0;
     for(ll i=2;i<=n;i++)
     {
        if(n%i==0 && x==0)
        {
            x=i;
            n/=i;
        }
        else if(n%i==0 && y==0)
        {
            y=i;
            n/=i;
            if(n!=y && n!=1 && x!=y && x!=n){z=n;
            cout<<"YES"<<endl;
            cout<<x<<" "<<y<<" "<<z<<endl;
            return 0;}
            else
            {
                break;
            }
        }

     }


      cout<<"NO"<<endl;
     return 0;
}
bool sov(ll a[500][500],ll n,ll m)
{
	map<ll,vector<ll> > mp;
	f(i,0,n)
       {
         f(j,0,m)
         {
			mp[j-i].push_back(a[i][j]);
		}
	}
	for(auto i : mp)
	{
		f(j,1,i.second.size())
		{
			if(i.second[j]!=i.second[0])
			return false;
		}
	}
	return true;
}
double getar(double a, double b, double c, double d, double e, double f)
{
    double dArea = ((c - a)*(f - b) - (e - a)*(d - b))/2.0;
    return (dArea > 0.0) ? dArea : -dArea;
}
int main()
{
int t;
cin>>t;
//t=1;
while(t--)
  {
    ll n;
    cin>>n;
        double a[n];
        f(i,0,n)
        {
            cin>>a[i];
        }
        set<double> s;
        f(i,0,n)
        {
            f(j,i+1,n)
            {
                s.insert(getar(0,1,a[i],0,a[j],0));
            }
        }
        cout<<s.size()<<endl;

  }
    return 0;
}


### Prompt

Your task is to create a Cpp solution to the following problem:

Argus was charged with guarding Io, which is not an ordinary cow. Io is quite an explorer, and she wanders off rather frequently, making Argus' life stressful. So the cowherd decided to construct an enclosed pasture for Io.

There are n trees growing along the river, where Argus tends Io. For this problem, the river can be viewed as the OX axis of the Cartesian coordinate system, and the n trees as points with the y-coordinate equal 0. There is also another tree growing in the point (0, 1). 

Argus will tie a rope around three of the trees, creating a triangular pasture. Its exact shape doesn't matter to Io, but its area is crucial to her. There may be many ways for Argus to arrange the fence, but only the ones which result in different areas of the pasture are interesting for Io. Calculate the number of different areas that her pasture may have. Note that the pasture must have nonzero area.

Input

The input consists of multiple test cases. The first line contains an integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow, each one is described in two lines.

In the first line of each test case there is a single integer n (1 ≤ n ≤ 50) denoting the number of trees growing along the river. Next line contains n distinct integers x_1 < x_2 < … < x_{n - 1} < x_n (1 ≤ x_i ≤ 50), the x-coordinates of trees growing along the river.

Output

In a single line output an integer, the number of different nonzero areas that triangles with trees as vertices may have.

Example

Input


8
4
1 2 4 5
3
1 3 5
3
2 6 8
2
1 2
1
50
5
3 4 5 6 8
3
1 25 26
6
1 2 4 8 16 32


Output


4
2
3
1
0
5
3
15

Note

In the first test case, we have 6 non-degenerate triangles with the following areas: 0.5, 0.5, 1, 1.5, 1.5 and 2. The pasture can have 4 different areas, and thus 4 is the answer.

In the second test case, we have 3 non-degenerate triangles with the following areas: 1, 1 and 2. The pasture can have 2 different areas, so 2 is the answer.

The following two drawings present the situation in the second test case. The blue triangles in the first drawing have area 1. The red triangle in the second drawing has area 2.

<image>

### Response

```cpp
#include<bits/stdc++.h>
#include <algorithm>
#define mod 1000000007
#define ll long long
#define ull unsigned long long
#define f(i,a,n) for(ll i=a;i<n;i++)
#define vec vector<ll>
#define mxh priority_queue<pair<int,int>>
#define mh priority_queue<int,vector<int>,greater<int>>
#define omap map<ll,ll>
#define umap unordered_map<ll,ll>
#define vpair vector<pair<ll,ll> >
#define pb push_back
#define mp make_pair
#define sor(v) sort(v.begin(),v.end())
#define fi  first
#define se second
//#include <boost/math/common_factor.hpp>

using namespace std;
ll ipow(ll base, ll exp)
{
    ll result = 1;
    for (;;)
    {
        if (exp & 1)
            result= (result*base)%mod;
        exp >>= 1;
        if (!exp)
            break;
        base= (base*base)%mod;
    }

    return result;
}
bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}
ll fact(ll n)
{
    if (n >= mod)
        return 0;

    ll result = 1;
    for (int i = 1; i <= n; i++)
        result = (result * i) % mod;

    return result;
}
bool is_prime(ll n) {
    if (n == 1) {
        return false;
    }
    ll i = 2;
    while (i*i <= n) {
        if (n % i == 0) {
            return false;
        }
        i += 1;
    }
    return true;
}
bool areRotations(string str1, string str2)
{
   /* Check if sizes of two strings are same */
   if (str1.length() != str2.length())
        return false;

   string temp = str1 + str1;
  return (temp.find(str2) != string::npos);
}
bool pow2 (ll x)
{
    return x && (!(x&(x-1)));
}
ll maxXorSum(ll n, ll k)
{
    if (k == 1)
        return n;
    ll res = 1;
    while (res <= n)
        res <<= 1;

    // Return res - 1 which denotes
    // a number with all bits set to 1
    return res - 1;
}
ll mcost(ll a[], ll n)
{

    ll y;
    if (n % 2 == 1)
        y = a[n / 2];
    else
        y = (a[n / 2] + a[(n - 2) / 2]) / 2;

    ll s = 0;
    for(ll i = 0; i < n; i++)
        s += abs(a[i] - y);

    return s;
}
ll largest_subarray(ll a[], ll n)
{
    unordered_map<ll, ll> index;
    ll ans = 0;
    for (ll i = 0, j = 0; i < n; i++) {

        j = max(index[a[i]], j);
        ans = max(ans, i - j + 1);
        index[a[i]] = i + 1;
    }
    return ans;
}
ll b[101],sz;
pair<ll,ll> adj[101];

void dfs(int s)
{
    b[s]=1;
    for(int i=1;i<=sz;i++)
    {    if(!b[i] && (adj[s].first==adj[i].first || adj[s].second==adj[i].second))
            dfs(i);
    }
}
void display(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        cout << a[i] << "  ";
    }
    cout << endl;
}
void per(int a[], int n)
{  ll d=0;
    sort(a, a + n);
  //  cout << "Possible permutations are:\n";
    do { ll s=0,x=1;
        f(i,0,n)
        {
            s+=a[i];
            if(s==0)
            {
                x=-1;
            }
        }
        if(x==1)
        {    cout<<"YES"<<endl;
        d=1;
            f(i,0,n)
           {
             cout<<a[i]<<" ";
           }cout<<endl;
          break;
        }
    } while (next_permutation(a, a + n));
    if(d==0)
    {
        cout<<"NO"<<endl;
    }
}
int gcd(int a, int b)
{
    if (b == 0)
        return a;

    else
        return gcd(b, a % b);
}

bool leftRotate(int a[], int d, int n)
{

    d = d % n;
    int g_c_d = gcd(d, n);
    for (int i = 0; i < g_c_d; i++) {
        int temp = a[i];
        int j = i;

        while (1) {
            int k = j + d;
            if (k >= n)
                k = k - n;

            if (k == i)
                break;

            a[j] = a[k];
            j = k;
        }
        a[j] = temp;
    }
    ll s=0,x=1;
    f(i,0,n)
    {
        s+=a[i];
        if(s==0)
        {
            x=0;
        }
    }
    if(x==1)
    {   cout<<"YES"<<endl;
        f(i,0,n)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
      return true;
    }
    return false;

}
ll rec(ll n,ll k)
{
    if(n==1)
    {
        return 1;
    }
    if (k==1)
    {
        return n;
    }
    return ((n+rec(n-1,k-1))%mod);
}

bool isPerfectSquare(ll x)
{
  if(sqrt(x)*sqrt(x)==x)
  {
      return true;
  }
  return false;
}
bool isSubSequence(string str1,string str2, int m, int n)
{
   int j = 0,x=0,d=0;
    if(str1[0]==str2[0])
    {
        for (int i=0; i<n&&j<m; i++)
       {
           if (str1[j] == str2[i])
            {
              j++;

            }
           else
            {   d=i;
                break;
            }
       }
       if(j==m)
       {
           return true;
       }
       ll p=9,v=0;
       for(int i=n-1;i>=d;i--)
        {  //  cout<<"l";
            if(v==10-j)
            {
                break;
            }
            if(str1[p]==str2[i])
            {
                p--;
                v++;
            }

            else
            {
                break;
            }
        }
       //cout<<j<<" "<<v<<" "<<d<<endl;
        if(v+j==10)
        {
            return true;
        }
        else
        {
            return false;
        }


    }
    else{
         size_t found = str2.find(str1);
        if (found != string::npos && str1[9]==str2[n-1])
         {
             return true;
         }
         else
         {
             return false;
         }
    }

}
ll countBits(ll n)
{
   ll count = 0;
   while (n)
   {
        count++;
        n >>= 1;
    }
    return count;
}
void kFactors(int n, int k)
{
    // A vector to store all prime factors of n
    vector<int> P;

    // Insert all 2's in vector
    while (n%2 == 0)
    {
        P.push_back(2);
        n /= 2;
    }

    // n must be odd at this point
    // So we skip one element (i = i + 2)
    for (int i=3; i*i<=n; i=i+2)
    {
        while (n%i == 0)
        {
            n = n/i;
            P.push_back(i);
        }
    }

    // This is to handle when n > 2 and
    // n is prime
    if (n > 2)
        P.push_back(n);

    // If size(P) < k, k factors are not possible
    if (P.size() < k)
    {
        cout << "-1" << endl;
        return;
    }

    // printing first k-1 factors
    for (int i=0; i<k-1; i++)
        cout << P[i] << " ";

    // calculating and printing product of rest
    // of numbers
    int product = 1;
    for (int i=k-1; i<P.size(); i++)
        product = product*P[i];
    cout << product << endl;
}
ll fin(ll n)
{    ll x=0,y=0,z=0;
     for(ll i=2;i<=n;i++)
     {
        if(n%i==0 && x==0)
        {
            x=i;
            n/=i;
        }
        else if(n%i==0 && y==0)
        {
            y=i;
            n/=i;
            if(n!=y && n!=1 && x!=y && x!=n){z=n;
            cout<<"YES"<<endl;
            cout<<x<<" "<<y<<" "<<z<<endl;
            return 0;}
            else
            {
                break;
            }
        }

     }


      cout<<"NO"<<endl;
     return 0;
}
bool sov(ll a[500][500],ll n,ll m)
{
	map<ll,vector<ll> > mp;
	f(i,0,n)
       {
         f(j,0,m)
         {
			mp[j-i].push_back(a[i][j]);
		}
	}
	for(auto i : mp)
	{
		f(j,1,i.second.size())
		{
			if(i.second[j]!=i.second[0])
			return false;
		}
	}
	return true;
}
double getar(double a, double b, double c, double d, double e, double f)
{
    double dArea = ((c - a)*(f - b) - (e - a)*(d - b))/2.0;
    return (dArea > 0.0) ? dArea : -dArea;
}
int main()
{
int t;
cin>>t;
//t=1;
while(t--)
  {
    ll n;
    cin>>n;
        double a[n];
        f(i,0,n)
        {
            cin>>a[i];
        }
        set<double> s;
        f(i,0,n)
        {
            f(j,i+1,n)
            {
                s.insert(getar(0,1,a[i],0,a[j],0));
            }
        }
        cout<<s.size()<<endl;

  }
    return 0;
}


```