#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
ll MOD=998244353;
ll dp[55][55][55][3];
int n,m,K,q,w[233];
bool road[233][233];
int Abs(int a) {if(a<0) a=-a; return a;}
void sol()
{
    scanf("%d%d%d%d",&n,&m,&K,&q);
    for(int i=1;i<=n;i++) scanf("%d",w+i);
    memset(road,0,sizeof(road));
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        road[a][b]=1;
    }
    memset(dp,0,sizeof(dp));
    for(int i=n;i>=1;i--)
    {
        for(int j=n;j>=1;j--)
        {
            for(int k=n;k>=1;k--)
            {
                for(int p=0;p<3;p++)
                {
                    ll& tar=dp[i][j][k][p];
                    tar=0;
                    if(p==0&&(Abs(w[i]-w[j])>K||Abs(w[j]-w[k])>K||Abs(w[i]-w[k])>K))
                    {tar=0; continue;}
                    tar=!p;
                    if(p==0)
                    {
                        for(int g=i+1;g<=n;g++)
                        {
                            if(road[i][g]) tar+=dp[g][j][k][1], tar%=MOD;
                        }
                    }
                    else if(p==1)
                    {
                        for(int g=j+1;g<=n;g++)
                        {
                            if(road[j][g]) tar+=dp[i][g][k][2], tar%=MOD;
                        }
                    }
                    else
                    {
                        for(int g=k+1;g<=n;g++)
                        {
                            if(road[k][g]) tar+=dp[i][j][g][0], tar%=MOD;
                        }
                    }
                }
            }
        }
    }
    while(q--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        printf("%d\n",int(dp[x][y][z][0]%MOD));
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--) sol();
}