#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 65
#define M 10000
#define mod 998244353
#define V vet[e]
using namespace std;
int dp[N][N][N][4];
int n,m,K,q,num,head[M],a[M],vet[M],next[M];
int i,j,k,u,v,e,cas,q1,q2,q3;
void add(int u,int v)
{
    vet[++num]=v;
    next[num]=head[u];
    head[u]=num;
}
void Main()
{
    scanf("%d%d%d%d",&n,&m,&K,&q);
    for (i=1;i<=n;i++)scanf("%d",&a[i]);
    num=0;
    for(i=1;i<=n;i++)head[i]=0;
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(v,u);
    }
    memset(dp,0,sizeof dp);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            for (k=1;k<=n;k++)
                if (abs(a[i]-a[j])<=K && abs(a[j]-a[k])<=K && abs(a[k]-a[i])<=K)
                    dp[i][j][k][0]=1;
    for (i=n;i>=1;i--)
        for (j=n;j>=1;j--)
            for (k=n;k>=1;k--)
            {
                for (e=head[i];e;e=next[e])
                    (dp[V][j][k][1]+=dp[i][j][k][0])%=mod;
                for (e=head[j];e;e=next[e])
                    (dp[i][V][k][2]+=dp[i][j][k][1])%=mod;
                for (e=head[k];e;e=next[e])
                    if (abs(a[i]-a[j])<=K && abs(a[j]-a[V])<=K && abs(a[V]-a[i])<=K)
                        (dp[i][j][V][0]+=dp[i][j][k][2])%=mod;
            }
    while (q--)
    {
        scanf("%d%d%d",&q1,&q2,&q3);
        printf("%d\n",dp[q1][q2][q3][0]);
    }
}
int main()
{
    scanf("%d",&cas);
    while (cas--)
        Main();
}