#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 60
#define MOD 998244353
using namespace std;
int n,m,K,Q,edgenum,u,v;
int a[N],head[N],next[N*100],vet[N*100];
int dp[N][N][N][4];
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||'9'<ch){if (ch=='-') f=-1;ch=getchar();}
    while ('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void add(int u,int v)
{
    vet[++edgenum]=v;
    next[edgenum]=head[u];
    head[u]=edgenum;
}
void solve()
{
    n=read();m=read();K=read();Q=read();
    for (int i=1;i<=n;i++) a[i]=read();
    edgenum=0;
    memset(head,0,sizeof(head));
    for (int i=1;i<=m;i++)
    {
        u=read();v=read();
        add(v,u);
    }
    memset(dp,0,sizeof(dp));
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            for (int 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 (int i=n;i>=1;i--)
        for (int j=n;j>=1;j--)
            for (int k=n;k>=1;k--)
            {
                for (int e=head[i];e;e=next[e])
                {
                    int v=vet[e];
                    (dp[v][j][k][1]+=dp[i][j][k][0])%=MOD;
                }
                for (int e=head[j];e;e=next[e])
                {
                    int v=vet[e];
                    (dp[i][v][k][2]+=dp[i][j][k][1])%=MOD;
                }
                for (int e=head[k];e;e=next[e])
                {
                    int v=vet[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--)
    {
        int a=read(),b=read(),c=read();
        printf("%d\n",dp[a][b][c][0]);
    }
}
int main()
{
    int T=read();
    while (T--) solve();
}