#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <limits.h>
#include <assert.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <list>
#include <bitset>
#include <vector>
using namespace std;

#define LL __int64

#define fi first
#define se second
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
#define ls id<<1
#define rs id<<1|1
#define MID(a,b) (((a)+(b))>>1)
#define maxx(a,b) ((a)<(b)?(b):(a))
#define minx(a,b) ((a)<(b)?(a):(b))
#define absx(a) ((a)<0?-(a):(a))
#define mk(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define itr iterator
#define lowbit(x) ((x)&-(x))

typedef unsigned LL ULL;
typedef unsigned uint;
typedef map<int,int> mii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<LL,LL> pll;
typedef vector<int> vi;

template< typename T >
inline void read(T &res)
{
    T x=0;
    bool f=0;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')f=!f;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    res = f ? -x : x ;
}

template< typename T >
inline void Max(T &a, T b)
{
    if(a<b) a=b;
}
template< typename T >
inline void Min(T &a, T b)
{
    if(b<a) a=b;
}

const double pi=(double) acos(-1.0);
const int MOD=(int) 1e9+7;
const int INF=(int) 0x3f3f3f3f;
const LL  LINF=(LL) INF<<32|INF;
const int SINF=(uint) ~0>>1;
const LL  SLINF=(ULL) (-1)>>1;
const double DINF=(double) 1e50;
const double eps=(double) 1e-8;
const int maxn=(int) 2e5+20;
const int maxm=(int) 3e4+15;

inline int sig(double x)
{
    return x<-eps?-1:x>eps;
}
inline void fadd(LL &x,LL a)
{
    x+=a;
    if(x>=MOD) x-=MOD;
}

//--------------start------------------

const int N=50+10;
const int mod=998244353;
struct Edge
{
    int v,next;
    Edge(int v=-1,int next=-1):v(v),next(next) {}
} e[N*N];
int head[N],total;
void init()
{
    memset(head,-1,sizeof(head));
    total=0;
}
void adde(int u,int v)
{
    e[total]=Edge(v,head[u]);
    head[u]=total++;
}

queue<int> qq;
int sta[N],rk[N];
int dp[N][N][N][5];
int n,m,K,Q;
int aa[N];

int fun(int x=-1,int y=-1,int z=-1)
{
    if(abs(x-y)>K)return 0;
    if(z==-1)return 1;
    if(abs(x-z)>K)return 0;
    if(abs(y-z)>K)return 0;
    return 1;
}
int du[N];

void work()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&K,&Q);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&aa[i]);
        }
        init();
        memset(du,0,sizeof(du));
        for(int i=0; i<m; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            adde(u,v);
            du[v]++;
        }
        while(!qq.empty())qq.pop();
        for(int i=1; i<=n; i++)
        {
            if(!du[i])
            {
                qq.push(i);
            }
        }
        int top=n;
        while(!qq.empty())
        {
            int u=qq.front();
            qq.pop();
            sta[top--]=u;
            for(int i=head[u]; i!=-1; i=e[i].next)
            {
                int v=e[i].v;
                du[v]--;
                if(!du[v])
                {
                    qq.push(v);
                }
            }
        }
        for(int i=1; i<=n; i++)
        {
            rk[sta[i]]=i;
        }
        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++)
                {
                    dp[i][j][k][0]=fun(aa[sta[i]],aa[sta[j]],aa[sta[k]]);
                    for(int i1=0; i1<3; i1++)
                    {
                        if(i1==0)
                        {
                            if(!fun(aa[sta[i]],aa[sta[j]],aa[sta[k]]))continue;
                            for(int i2=head[sta[i]]; i2!=-1; i2=e[i2].next)
                            {
                                int v=rk[e[i2].v];
                                dp[i][j][k][0]+=dp[v][j][k][1];
                                dp[i][j][k][0]%=mod;
                            }
                        }
                        else if(i1==1)
                        {
                            if(!fun(aa[sta[j]],aa[sta[k]]))continue;
                            for(int i2=head[sta[j]]; i2!=-1; i2=e[i2].next)
                            {
                                int v=rk[e[i2].v];
                                if(!fun(aa[sta[i]],aa[e[i2].v]))continue;
                                dp[i][j][k][1]+=dp[i][v][k][2];
                                dp[i][j][k][1]%=mod;
                            }
                        }
                        else
                        {
                            if(!fun(aa[sta[i]],aa[sta[j]]))continue;
                            for(int i2=head[sta[k]]; i2!=-1; i2=e[i2].next)
                            {
                                int v=rk[e[i2].v];
                                if(!fun(aa[sta[i]],aa[sta[j]],aa[e[i2].v]))continue;
                                dp[i][j][k][2]+=dp[i][j][v][0];
                                dp[i][j][k][2]%=mod;
                            }
                        }
                    }
                }
            }
        }

        for(int i=0; i<Q; i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            a=rk[a],b=rk[b],c=rk[c];
            printf("%d\n",dp[a][b][c][0]);
        }
    }
}

//--------------end--------------------

//#define yukihana0416
int main()
{
#ifdef yukihana0416
    freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif // yukihana0416
    work();
    return 0;
}