#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define LL long long
#define ULL unsigned long long
//#define pil pair <int, LL>
#define pii pair <ULL, ULL>
//#define pii pair <int, int>
#define xx first
#define yy second
using namespace std;

const int N = 55, mod = 998244353;

int n, m, k, q;
int a[N];
int dp[N][N][N][3], ok[N][N], mp[N][N];
//vector <int> g[N];

bool cmp (int x, int y) { return a[x] < a[y]; }

int jug (int x, int y) { return abs (a[x] - a[y]) <= k; }

inline void add (int &x ,int y) {
    x += y;
    if (x >= mod) x -= mod;
}

int main () {
//    freopen ("in.txt", "r", stdin);
    int T;
    cin >> T;
    while (T--) {
        int u, v;
        cin >> n >> m >> k >> q;
        for (int i = 1; i <= n; i++) {
            scanf ("%d", &a[i]);
        }
        memset (mp, 0, sizeof mp);
        for (int i = 1; i <= m; i++) {
            scanf ("%d%d", &u, &v);
            mp[u][v] = 1;
//            g[u].push_back (v);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                ok[i][j] = jug (i, j);
            }
        }
        memset (dp, 0, sizeof dp);
//        dp[n][n][n][0] = 1;
//        for (int i = 1; i <= n; i++) sort (g[i].begin(), g[i].end(), cmp);
        for (int i = n; i >= 1; i--) {
            for (int j = n; j >= 1; j--) {
                for (int k = n; k >= 1; k--) {
                    for (int l = 2; l >= 0; l--) {
                        if (l == 0 && ok[i][j] && ok[i][k] && ok[j][k]) dp[i][j][k][l] = 1;
                        if (l == 2) u = k;
                        else if (l == 1) u = j;
                        else u = i;
                        int ll = (l + 1) % 3;
                        for (int o = 1; o <= n; o++) if (mp[u][o]) {
//                            if (i == 4 && j == 4 && k == 3 && l == 2) cout << u << ' ' << ll << ' ' << o << endl;
                            if (l == 2) {
                                if (ok [o][i] && ok[o][j]) add (dp[i][j][k][l], dp[i][j][o][ll]);
                            } else if (l == 1) {
                                if (ok [o][i]) add (dp[i][j][k][l], dp[i][o][k][ll]);
                            } else {
                                add (dp[i][j][k][l], dp[o][j][k][ll]);
                            }
                        }
//                        if (dp[i][j][k][l]) cout << i << ' ' << j << ' ' << k << ' ' << l << ' ' << dp[i][j][k][l] << endl;
                    }
                }
            }
        }
        while (q--) {
            int a, b, c;
            scanf ("%d%d%d", &a, &b, &c);
            printf ("%d\n", dp[a][b][c][0]);
        }
    }
}