D

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
        cin>>n;
        int arr[100000];
        for (int i=0;i<n;i++) cin>>arr[i];
        int sum1[100001];
        int sum2[100001];
        int c1=0,c2=0;
        sum1[0]=0,sum2[0]=0;
        for (int i=0;i<n;i++)
        {
            if (arr[i]==1) c1++;
            if (arr[i]==2) c2++;
            sum1[i+1]=c1;
            sum2[i+1]=c2;
        }

        int q;
        cin>>q;
        while(q--)
        {
            int l,r,k;
            cin>>l>>r>>k;
            int p1,p2;
            p1=sum1[r]-sum1[l-1];
            p2=sum2[r]-sum2[l-1];
            int ab=r-l+1;
            if (p1>p2) swap(p1,p2);
            int c=0;
            int ar=min(k-c,min(ab-(p1+p2),p2-p1));
            p1+=ar;
            c+=ar;
            if ((p1+p2)==ab)
            {
                int q=min(k-c,(p2-p1)/2);
                p2-=q;
                p1+=q;
                c+=q;
            }
            else
            {
                int diff=min(ab-(p1+p2),k-c);
                p2+=diff/2+diff%2;
                p1+=diff/2;
            }
            long long r1=(long long)p1;
            long long r2=(long long)p2;
            long long r3=r2*r1;
            cout<<r3<<endl;
        }
	}
}