#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110;
int n,m,p,q,d[N][N][N],c[N][N][N],s[N][N][N];
int u,v,t,sum;
void judge () {
    memset(c,0,sizeof(c));
    for (int idx=2;idx<=t;idx++) {
        for (int k=1;k<=n;k++) {
            for (int i=1;i<=n;i++) {
                for (int j=1;j<=n;j++) {
                    if (k!=u&&k!=v) {   
                        c[idx][i][j]+=(d[idx-1][i][k]+d[1][k][j])%p;
                        c[idx][i][j]%p;
                        //cout << idx <<' '
                    }
                }    
            }    
        }
    }
    memcpy(d,c,sizeof(c));
}
int main () {
    freopen("messenger.in","r",stdin);
    freopen("messenger.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m >> p;
    for (int i=1;i<=m;i++) {
        int a,b;
        cin >> a >> b;
        s[1][a][b]=1;
    }
    cin >> q;
    while (q--) {
        memcpy(d,s,sizeof(s));
        cin >> u >> v >> t;
        judge();                                                           
        cout << d[t][u][v] <<endl;
        sum=0;
    }
    return 0;
}