// Arup Guha
// 7/30/2012
// Solution to Recitation Problem: Paths, using recursion.

#include <stdio.h>

#define MAX 10

int solve(int blocked[][2], int numBlocked, int start[], int end[]);
int equal(int loc1[], int loc2[]) ;
int in(int start[], int blocked[][2], int numBlocked);

int main() {

    FILE* ifp = fopen("paths.in", "r");

    int numCases;
    fscanf(ifp, "%d", &numCases);

    // Go through each case.
    int loop;
    for (loop=1; loop<=numCases; loop++) {

        int blocked[MAX][2];

        int i, numBlocked;
        fscanf(ifp, "%d", &numBlocked);

        // Read in the blocked locations.
        for (i=0; i<numBlocked; i++)
            fscanf(ifp, "%d%d", &blocked[i][0], &blocked[i][1]);

        printf("Data Set %d:\n\n", loop);

        int numTests;
        fscanf(ifp, "%d", &numTests);

        // Go through and solve each case for this grid.
        for (i=1; i<=numTests; i++) {
            int start[2], end[2];
            fscanf(ifp, "%d%d%d%d", &start[0], &start[1], &end[0], &end[1]);
            int answer = solve(blocked, numBlocked, start, end);
            if (answer == 1)
                printf("  Test Case %d: Nick can take 1 perfect path.\n", i);
            else
                printf("  Test Case %d: Nick can take %d perfect paths.\n", i, answer);
        }
        printf("\n");

    }

    fclose(ifp);
    return 0;
}

// Recursively returns the number of shortest paths from start to end which
// don't use any of the coordinates listed in blocked.
int solve(int blocked[][2], int numBlocked, int start[], int end[]) {

    // If we're starting from a blocked spot, we can't make it.
    if (in(start, blocked, numBlocked))
        return 0;

    // If we're there, there's one way to do it.
    if (equal(start, end))
        return 1;

    // Set our changes.
    int dx = 1, dy = 1;
    if (end[0] < start[0])
        dx = -1;
    if (end[1] < start[1])
        dy = -1;

    // Note: In each recursive call, since we are not making new start arrays, it's
    //       really important to return the array back to its original state after
    //       a recursive call finishes.

    // No recursion is really needed here, but, I'll call it anyway...
    if (start[0] == end[0]) {
        start[1] += dy;
        int answer = solve(blocked, numBlocked, start, end);
        start[1] -= dy;
        return answer;
    }

    // Same here.
    if (start[1] == end[1]) {
        start[0] += dx;
        int answer = solve(blocked, numBlocked, start, end);
        start[0] -= dx;
        return answer;
    }

    // Now try going both ways.
    start[0] += dx;
    int oneway = solve(blocked, numBlocked, start, end);
    start[0] -=dx;
    start[1] += dy;
    int otherway = solve(blocked, numBlocked, start, end);
    start[1] -= dy;

    // Here is our answer.
    return oneway + otherway;

}

// loc1, loc2 must be of size 2. Returns if both corresponding coordinates are equal.
int equal(int loc1[], int loc2[]) {
    return loc1[0] == loc2[0] && loc1[1] == loc2[1];
}

int in(int start[], int blocked[][2], int numBlocked) {

    // Return 1 if we find start on the illegal list.
    int i;
    for (i=0; i<numBlocked; i++)
        if (equal(start, blocked[i]))
            return 1;

    // If we make it here, we're okay.
    return 0;

}