#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int MAXN = 105;
const int MAXD = 55;

vector<int> G[MAXN]; 
int dp[MAXD][MAXN];  
int ans[MAXN][MAXN][MAXD]; 
int n, m, z, q;

int main(){
    freopen("messenger.in","r", stdin);
    freopen("messenger.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> z;
    for(int i = 0;i < m;i ++){
        int a, b; cin >> a >> b;
        G[a].push_back(b);
    }
    for(int u = 1;u <= n;u ++){
        for(int v = 1;v <= n;v ++){
            if(u == v) continue;
            for(int d = 1;d <= 50;d ++){
                memset(dp, 0, sizeof(dp));
                dp[0][u] = 1;
                for(int k = 0;k < d;k ++){
                    for(int x = 1;x <= n;x ++){
                        if(dp[k][x] == 0) continue;
                        for(int y : G[x]){
                            if(k < d - 1 && (y == u || y == v)) continue;
                            dp[k + 1][y] = (dp[k + 1][y] + dp[k][x]) % z;
                        }
                    }
                }
                ans[u][v][d] = dp[d][v] % z;
            }
        }
    }
    cin >> q;
    while(q --){
        int u, v, d;
        cin >> u >> v >> d;
        cout << ans[u][v][d] << '\n';
    }
    return 0;
}