#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = +;
const int mod = ;
int T,n,m,lim,q,tot,w[N],dp[N][N][N][],head[N];
struct Edge{
int v,next;
}edge[N*N/];
void add(int u,int v){
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot++;
}
inline void up(int &x,int y){
x+=y;if(x>=mod)x-=mod;
}
bool judge(int i,int j){
return abs(w[i]-w[j])<=lim;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d%d",&n,&m,&lim,&q);
for(int i=;i<=n;++i)scanf("%d",&w[i]);
memset(head,-,sizeof(head)),tot=;
for(int i=;i<m;++i){
int u,v;scanf("%d%d",&u,&v);add(v,u);
}
memset(dp,,sizeof(dp));
for(int i=n;i>;--i)
for(int j=n;j>;--j)
for(int k=n;k>;--k){
if(judge(i,j)&&judge(j,k)&&judge(k,i))
up(dp[i][j][k][],);
if(dp[i][j][k][])
for(int k1=head[i];~k1;k1=edge[k1].next)
up(dp[edge[k1].v][j][k][],dp[i][j][k][]);
if(dp[i][j][k][])
for(int k1=head[j];~k1;k1=edge[k1].next)
if(!judge(i,edge[k1].v))continue;
else up(dp[i][edge[k1].v][k][],dp[i][j][k][]);
if(dp[i][j][k][])
for(int k1=head[k];~k1;k1=edge[k1].next){
if(!judge(i,j)||!judge(i,edge[k1].v)||!judge(j,edge[k1].v))
continue;
up(dp[i][j][edge[k1].v][],dp[i][j][k][]);
}
}
while(q--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
printf("%d\n",dp[x][y][z][]);
}
}
return ;
}