#include<map>

#include<set>

#include<ctime>

#include<cmath>

#include<stack>

#include<queue>

#include<string>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define lowbit(x) (x & (-x))

typedef unsigned long long int ull;

typedef long long int ll;

const double pi = 4.0*atan(1.0);

const int inf = 0x3f3f3f3f;

const int maxn = 1e5+;

const int maxm = ;

const int mod = 1e9+;

using namespace std;

int n, m, tol, T;

int L;

int A[];

int M[][];

ll sx[];

ll sy[];

ll sum;

void init() {

    sum = ;

    memset(A, , sizeof A);

    memset(M, , sizeof M);

    memset(sx, , sizeof sx);

    memset(sy, , sizeof sy);

}

ll solve(int x, int y) {

    ll ans = ;

    int cx = x/L;

    int cy = y/L;

    ll t = 1ll * cx * cy;

    ans += 1ll * t * sum;

    int x1 = x % L;

    int y1 = y % L;

    ll s = ;

    for(int i=; i<=x1; i++)    s += sx[i];

    ans += s * cy;

    s = ;

    for(int i=; i<=y1; i++)    s += sy[i];

    ans += s * cx;

    for(int i=; i<=x1; i++) {

        for(int j=; j<=y1; j++) {

            ans += M[i][j];

        }

    }

    return ans;

}

int main() {

//    freopen("in.txt", "r", stdin);

//  freopen("out.txt", "w", stdout);

    scanf("%d", &T);

    while(T--) {

        init();

        scanf("%d", &L);

        for(int i=; i<L; i++)    scanf("%d", &A[i]);

        int cursor = ;

        for(int i=; i<=*L; i++) {

            for(int j=; j<=i; j++) {

                M[j][i - j + ] = A[cursor];

                cursor = (cursor + ) % L;

            }

        }

        L <<= ;

        for(int i=; i<=L; i++) {

            for(int j=; j<=L; j++) {

                sy[j] += M[i][j];

                sx[i] += M[i][j];

            }

            sum += sx[i];

        }

        /*

        for(int i=1; i<=L; i++)    for(int j=1; j<=L; j++)    printf("%d%c",M[i][j], j==L ? '\n' : ' \t');

        for(int i=1; i<=L; i++)    printf("sx%d = %d\n", i, sx[i]);

        for(int i=1; i<=L; i++)    printf("sy%d = %d\n", i, sy[i]);

        */

        int q;

        scanf("%d", &q);

        while(q--) {

            int x1, y1, x2, y2;

            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

            x1++, y1++, x2++, y2++;

            ll ans = solve(x2, y2);

            ans -= solve(x1-, y2);

            ans -= solve(x2, y1-);

            ans += solve(x1-, y1-);

            printf("%lld\n", ans);

        }

    }

    return ;

}