#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

inline int read()

{

    char c = getchar();  while(!isdigit(c)) c = getchar();

    int x = ;

    while(isdigit(c)) { x = x *  + c - ''; c = getchar(); }

    return x;

}

const int maxn=+;

int mod=;

int T,n,m,k,q,g[maxn][maxn],w[maxn],f[maxn][maxn][maxn][];

bool check(int a,int b,int c)

{

    if(abs(w[a]-w[b])>k) return ;

    if(abs(w[a]-w[c])>k) return ;

    if(abs(w[b]-w[c])>k) return ;

    return ;

}

int main()

{

    scanf("%d",&T); while(T--)

    {

        scanf("%d%d%d%d",&n,&m,&k,&q);

        memset(g,,sizeof g);

        for(int i=;i<=n;i++) scanf("%d",&w[i]);

        for(int i=;i<=m;i++)

        {

            int u,v; scanf("%d%d",&u,&v);

            g[u][v]=;

        }

        memset(f,,sizeof f);

        for(int i=n;i>=;i--)

        {

            for(int j=n;j>=;j--)

            {

                for(int k=n;k>=;k--)

                {

                    if(check(i,j,k)==) f[i][j][k][]=;

                    else f[i][j][k][]=(f[i][j][k][]+)%mod;

                    for(int s=;s<k;s++)

                        if(g[s][k]) f[i][j][s][]=(f[i][j][s][]+f[i][j][k][])%mod;

                    for(int s=;s<=j;s++)

                        if(g[s][j]) f[i][s][k][]=(f[i][s][k][]+f[i][j][k][])%mod;

                    for(int s=;s<=i;s++)

                        if(g[s][i]) f[s][j][k][]=(f[s][j][k][]+f[i][j][k][])%mod;

                }

            }

        }

        for(int i=;i<=q;i++)

        {

            int a,b,c; scanf("%d%d%d",&a,&b,&c);

            printf("%d\n",f[a][b][c][]);

        }

    }

    return ;

}