#include <bits/stdc++.h>
using namespace std;
#define maxn 100001
#define mod 1000000009
#define ll long long int

struct suffix
{
    ll index;
    ll rank[2];
};

ll cmp(struct suffix a, struct suffix b)
{
    return (a.rank[0] == b.rank[0])? (a.rank[1] < b.rank[1] ?1: 0):
           (a.rank[0] < b.rank[0] ?1: 0);
}

vector<ll> buildSuffixArray(ll txt[], ll n)
{
    struct suffix suffixes[n];
 
    for (ll i = 0; i < n; i++)
    {
        suffixes[i].index = i;
        suffixes[i].rank[0] = txt[i];
        suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1]): -1;
    }
 
    sort(suffixes, suffixes+n, cmp);
 
    ll ind[n];

    for (ll k = 4; k < 2*n; k = k*2)
    {
        ll rank = 0;
        ll prev_rank = suffixes[0].rank[0];
        suffixes[0].rank[0] = rank;
        ind[suffixes[0].index] = 0;
 
        for (ll i = 1; i < n; i++)
        {
            if (suffixes[i].rank[0] == prev_rank &&
                    suffixes[i].rank[1] == suffixes[i-1].rank[1])
            {
                prev_rank = suffixes[i].rank[0];
                suffixes[i].rank[0] = rank;
            }
            else
            {
                prev_rank = suffixes[i].rank[0];
                suffixes[i].rank[0] = ++rank;
            }
            ind[suffixes[i].index] = i;
        }
 
        for (ll i = 0; i < n; i++)
        {
            ll nextindex = suffixes[i].index + k/2;
            suffixes[i].rank[1] = (nextindex < n)?
                                  suffixes[ind[nextindex]].rank[0]: -1;
        }

        sort(suffixes, suffixes+n, cmp);
    }

    vector<ll>suffixArr;
    for (ll i = 0; i < n; i++)
        suffixArr.push_back(suffixes[i].index);
 
    return  suffixArr;
}

vector<ll> kasai(ll txt[], vector<ll> suffixArr)
{
    ll n = suffixArr.size();
 
    vector<ll> lcp(n, 0);
 
    vector<ll> invSuff(n, 0);
 
    for (ll i=0; i < n; i++)
        invSuff[suffixArr[i]] = i;
 
    ll k = 0;
 
    for (ll i=0; i<n; i++)
    {

        if (invSuff[i] == n-1)
        {
            k = 0;
            continue;
        }
 
        
        ll j = suffixArr[invSuff[i]+1];
 
        while (i+k<n && j+k<n && txt[i+k]==txt[j+k])
            k++;
 
        lcp[invSuff[i]] = k;  
        
        if (k>0)
            k--;
    }
 
    
    return lcp;
}

int main(){
	ll t, ans, n, heights[maxn];
	cin >> t;
	std::vector<ll> suffarr, lcparr;

	while(t--){
		cin >> n;
		for (ll i = 0; i < n; ++i)
		{
			cin >> heights[i];
		}
		for (ll i = 1; i < n; ++i)
		{
			heights[i-1] = heights[i] - heights[i-1];
		}
		n--;
		suffarr = buildSuffixArray(heights, n);
		lcparr = kasai(heights, suffarr);
		ans = (n- suffarr[0])%mod;
		for (ll i = 1; i < n; ++i)
		{
			ans = (ans + (n-suffarr[i] - lcparr[i-1])%mod)%mod;
		}
		/*for (int i = 0; i < n; ++i)
		{
			cout << suffarr[i] << " ";
		}
		cout << endl;
		for (int i = 0; i < n; ++i)
		{
			cout << lcparr[i] << " ";
		}
		cout << endl;*/
		cout << ans << endl;
		suffarr.clear();
		lcparr.clear();
	}





	return 0;
}