#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=35,M=5e5+10,V=50;
struct node{int y,k,id;};
vector<node>vec[N];
vector<int>G[N];
int f[N][N][55],n,m,mod,q,ans[M];
int main(){
    freopen("messenger.in","r",stdin);
    freopen("messenger.out","w",stdout); 
    scanf("%d %d %d",&n,&m,&mod);
    for(int i=1;i<=m;i++){
        int u,v;scanf("%d %d",&u,&v);
        G[v].push_back(u);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        int x,y,k;
        scanf("%d %d %d",&x,&y,&k);
        vec[x].push_back(node{y,k,i});
    }
    for(int s=1;s<=n;s++){
        for(int j=1;j<=n;j++){
            f[s][j][0]=1;
            //cout<<s<<"-"<<j<<" "<<0<<" "<<f[s][j][0]<<endl;
        }
        for(int k=1;k<=V;k++){
            for(int i=1;i<=n;i++){
                if(s==i)continue;
                for(int j=1;j<=n;j++){
                    for(auto pre:G[i]){
                        if(j==pre)continue;
                        f[i][j][k]+=f[pre][j][k-1];
                        f[i][j][k]%=mod; 
//                        if(s==5&&i==3&&j==3&&k==6){
//                            cout<<pre<<" "<<j<<" "<<k-1<<" "<<f[pre][j][k-1]<<endl;
//                        }
//                        if(s==5&&i==2&&j==3&&k==5){
//                            cout<<pre<<" "<<j<<" "<<k-1<<" "<<f[pre][j][k-1]<<endl;
//                        }
//                        if(s==5&&i==1&&j==3&&k==4){
//                            cout<<pre<<" "<<j<<" "<<k-1<<" "<<f[pre][j][k-1]<<endl;
//                        }
//                        if(s==5&&i==4&&j==3&&k==3){
//                            cout<<pre<<" "<<j<<" "<<k-1<<" "<<f[pre][j][k-1]<<endl;
//                        }
//                        if(s==5&&i==2&&j==3&&k==2){
//                            cout<<pre<<" "<<j<<" "<<k-1<<" "<<f[pre][j][k-1]<<endl;
//                        }
//                        if(s==5&&i==1&&j==3&&k==1){
//                            cout<<pre<<" "<<j<<" "<<k-1<<" "<<f[pre][j][k-1]<<endl;
//                        }
                    } 
                    //cout<<i<<" "<<j<<" "<<k<<" "<<f[i][j][k]<<endl;
                }
            }
        }
        for(auto sta:vec[s]){
            int id=sta.id,y=sta.y,k=sta.k;
            ans[id]=f[y][y][k];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int k=0;k<=V;k++){
                    f[i][j][k]=0;
                }
            }
        }
    }
    for(int i=1;i<=q;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
} 
/*
5 7 10
1 2
2 3
3 4
4 5
5 1
2 4
4 1
2
2 1 3
5 3 6
*/