#include <iostream> #include <cstring> #include <cstdio> #define MAX 35 using namespace std; struct matrix { int num[MAX][MAX]; matrix() { memset(num,0,sizeof(num)); } }; int n; long long map[MAX][MAX]; matrix A[10005]; long long city[35]; matrix operator*(matrix &a,matrix &b) { matrix t; int i,j,k; for(i=0;i<n;i++) for(j=0;j<n;j++) { t.num[i][j]=0; for(k=0;k<n;k++) t.num[i][j]+=(a.num[i][k]*b.num[k][j]); t.num[i][j]%=2008; } return t; } void init() { int i,j; for(i=0;i<n;i++) { for(j=0;j<n;j++) { A[0].num[i][j]=map[i][j]; } } } int main() { int nn; int Find(int u); while(scanf("%d",&nn)!=EOF) { int i; memset(map,0,sizeof(map)); memset(city,0,sizeof(city)); n=0; for(i=0;i<nn;i++) { int u,v; scanf("%d%d",&u,&v); int lo1=Find(u); int lo2=Find(v); map[lo1][lo2]++; } int k; init(); for(i=1;i<10005;i++) A[i]=A[i-1]*A[0]; scanf("%d",&k); while(k--) { int v1,v2,t1,t2; scanf("%d%d%d%d",&v1,&v2,&t1,&t2); if(t1>t2) { int t=t1; t1=t2; t2=t; } int l=n; int l1=Find(v1); int l2=Find(v2); if(l1>=l||l2>=l) { printf("0\n"); n=l; continue; } int sum=0; for(i=t1-1;i<t2;i++) sum=(sum%2008+A[i].num[l1][l2]%2008)%2008; printf("%d\n",sum); } } return 0; } int Find(int u) { int i; for(i=0;i<n;i++) { if(city[i]==u) break; } if(i>=n) { n++; city[i]=u; return i; } else { return i; } }