#include<algorithm>

#include<cmath>

#include<cstring>

#include<cstdlib>

#include<iostream>

using namespace std;

const int maxn=105;

struct Mat{

int mat[maxn][maxn];

}map,f;

int m,n,q,l;

Mat operator *(Mat a,Mat b){

Mat c;

memset(c.mat,0,sizeof(c.mat));

int i,j,k;

for(k=1;k<=n;k++){

for(i=1;i<=n;i++){

for(j=1;j<=n;j++){

c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];

}

}

}

return c;

}

Mat operator ^(Mat a,int k){

Mat c;

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

c.mat[i][j]=(i==j);

}

}

while(k){

if(k&1)c=c*a;

k/=2;

a=a*a;

}

return c;

}

int main(){

int a,b;

int i=0;

scanf("%d%d%d",&n,&m,&l);

memset(map.mat,0,sizeof(map.mat));

memset(f.mat,0,sizeof(f.mat));

while(m--){

scanf("%d%d",&a,&b);

++map.mat[a][b];

}

f=map^l;

scanf("%d",&q);

while(q--){

scanf("%d%d",&a,&b);

printf("%d\n",f.mat[a][b]);

}

return 0;

}