#include <bits/stdc++.h>
using namespace std;
const int N = 110,M = 1e4+10;
int n,m,z,q;
struct made{
    int ver,nx;
}e[M<<1],re[M<<1];
int hd[N],rhd[N],tot,rtot;
void add(int x,int y){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],hd[x] = tot;
}
void radd(int x,int y){
    rtot++;
    re[rtot].ver = y,re[rtot].nx = rhd[x],rhd[x] = rtot;
}
//void tarjan(int x){
//    low[x] = dfn[x] = ++cnt;
//    st[++top] = x,v[x] = 1;
//    for(int i = hd[x];i;i = e[i].nx){
//        int y = e[i].ver;
//        if(!dfn[y])tarjan(y),low[x] = min(low[x],low[y]) ;
//        else if(v[y])low[x] = min(low[x],dfn[y]);
//    }
//    if(low[x] == dfn[x]){
//        num++;int y = 0;
//        do{
//            y = st[top--];
//            v[y] = 0,c[y] = num;
//            size[num]++,scc[num].push_back(y);
//        }while(x != y);
//    }
//}寄 祭tarjan 
long long f[N][N][60],g[N][N][60];
int main(){
    freopen("messenger.in","r",stdin);
    freopen("messenger.out","w",stdout);
    scanf("%d%d%d",&n,&m,&z);
    for(int i = 1;i <= m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        radd(y,x);
        f[x][y][1] = 1;
    }
    for(int i = 2;i <= 6;i++){
//        if(i == 3){
//            i = 3;
//            
//        }
        for(int x = 1;x <= n;x++){
            for(int y = 1;y <= n;y++){
                if(x == y)continue;
                for(int u = hd[x];u;u = e[u].nx){
                    int k = e[u].ver;
                    if(x == k || y == k)continue;
                    f[x][y][i] = (long long)(f[x][y][i] +(f[x][k][1] * f[k][y][i-1]) % z) % z;
                    g[x][y][i] = f[x][y][i];
                    if(!f[x][y][i])continue;
                    for(int w = rhd[x];w;w = re[w].nx){
                        int h = re[w].ver;
                        for(int w = 1;w < i-1;w++){
                            g[x][y][i] -= (f[k][h][w] * f[h][x][1] * f[x][y][i-2-w]) % z;
                            g[x][y][i] %= z;
                        } 
                    }
                }  
            }
        }
    }
    scanf("%d",&q);
    for(int i = 1;i <= q;i++){
        int x,y,d;
        scanf("%d%d%d",&x,&y,&d);
        printf("%lld\n",g[x][y][d]%z);
    }
    
    return 0;
    
}