#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int q,g[N][N],n,m,mod,pre[N][N][N];//pre 从u到v走几步的方案数 

vector<int> adj[N]; 

int main(){
	freopen("messenger.in","r",stdin);
	freopen("messenger.out","w",stdout);
	scanf("%d%d%d",&n,&m,&mod);
	memset(g,0,sizeof(g));
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u][v]=1;
		adj[u].push_back(v);
	}
	
	for(int u=1;u<=n;u++){
		for(int v=1;v<=n;v++){
			if(u==v)continue;
			
			vector <int> m_p;
			for(int i=1;i<=n;i++){
				if(i!=u&&i!=v)m_p.push_back(i);
			}
			
			pre[u][v][1]=g[u][v]%mod;
			
			int dppre[N];//初始化从u一步走到i的方案 
			
			for(int i=1;i<=n;i++){
				dppre[i]=g[u][i]%mod;
			} 
			
			for (int k = 2; k <= 50; ++k) {
                int dp_ct[N] = {0};

                for (vector<int>::iterator it = m_p.begin(); it != m_p.end(); ++it) {
                    int y = *it;
                    int val = dppre[y];
                    if (val == 0) continue;

                    for (vector<int>::iterator x_it = adj[y].begin(); x_it != adj[y].end(); ++x_it) {
                        int x = *x_it;
                        dp_ct[x] = (dp_ct[x] + val) % mod;
                    }
                }

                pre[u][v][k] = dp_ct[v] % mod;

                
                memcpy(dppre, dp_ct, sizeof(dp_ct));
            }
		}
	}
	scanf("%d",&q);
	while(q--){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		printf("%d\n",pre[x][y][z]%mod);
	} 
	return 0;
}