#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define mp(a,b) make_pair(a,b)
using namespace std;
typedef long long LL;
typedef double db;
int dp[55][55][55][3];
const int mod=998244353;
int x[55];
vector<int>g[55];
int k;
int dfs(int a,int b,int c,int no){
    if(dp[a][b][c][no]!=-1) return dp[a][b][c][no];
    int ans=0;
    if(no==0&&(abs(x[a]-x[b])>k||abs(x[a]-x[c])>k||abs(x[b]-x[c])>k)){
        return dp[a][b][c][no]=0;
    }
    if(no==0){
        ans++;
    }
    if(no==0){
        int p=g[a].size();
        for(int i=0;i<p;i++){
            int v=g[a][i];
            ans+=dfs(v,b,c,no+1);
            ans%=mod;
        }
    }
    else if(no==1){
        int p=g[b].size();
        for(int i=0;i<p;i++){
            int v=g[b][i];
            ans+=dfs(a,v,c,no+1);
            ans%=mod;
        }
    }
    else{
        int p=g[c].size();
        for(int i=0;i<p;i++){
            int v=g[c][i];
            ans+=dfs(a,b,v,0);
            ans%=mod;
        }
    }
    return dp[a][b][c][no]=ans;
}
int main()
{
    int t,n,m,q;
    cin>>t;
    while (t--) {
        scanf("%d%d%d%d",&n,&m,&k,&q);
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=1;i<=n;i++) scanf("%d",&x[i]);
        for(int i=0;i<m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            g[x].push_back(y);
        }
        memset(dp,-1,sizeof(dp));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int f=1;f<=n;f++){
                    if(dp[i][j][f][0]==-1) dfs(i,j,f,0);
                }
            }
        }
        for(int i=0;i<q;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            printf("%d\n",dp[x][y][z][0]);
        }
    }
}