You have to find the number of solutions of the following equation:

Ax + By + C = 

Where A, B, C, x, y are integers and x1 ≤ x ≤ x2 and y1 ≤ y ≤ y2.

Input

Input starts with an integer T (≤ ), denoting the number of test cases.

Each case starts with a line containing seven integers A, B, C, x1, x2, y1, y2 (x1 ≤ x2, y1 ≤ y2). The value of each integer will lie in the range [-, ].

Output

For each case, print the case number and the total number of solutions.

Sample Input

  - -

- -  -  -

  -

- -  -  -

  -

Output for Sample Input

Case :

Case :

Case :

Case :

Case : 

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<math.h>

#include<queue>

#include<stack>

#include <map>

#include <string>

#include <vector>

#include<iostream>

using namespace std;

#define N 10006

#define INF 0x3f3f3f3f

#define LL long long

#define mod 1000000007

LL ex_gcd(LL a,LL b,LL &x,LL &y)

{

    if(b==)

    {

        x = ;

        y = ;

        return a;

    }

    LL g = ex_gcd(b,a%b,x,y);

    LL t = x;

    x = y;

    y = t- a/b * y;

    return g;

}

int sign(LL n)

{

    if(n==)

        return ;

    return n>?:-;

}

LL ceil(LL a,LL b)

{

    int s = sign(a) * sign(b);

    return b/a + (b%a!= && s>);

}

LL floor(LL a,LL b)

{

    int s = sign(a) * sign(b);

    return b/a - (b%a!= && s<);

}

int main()

{

    int T,con=;

    scanf("%d",&T);

    LL a,b,c,x1,x2,y1,y2,x,y;

    while(T--)

    {

        scanf("%lld %lld %lld %lld %lld %lld %lld",&a,&b,&c,&x1,&x2,&y1,&y2);

        printf("Case %d: ",con++);

        if(a== && b==)

        {

            if(c==)

            {

                printf("%lld\n",(x2-x1+)*(y2-y1+));

            }

            else

                printf("0\n");

            continue;

        }

        if(a==)

        {

            if(c%b!=)

            {

                printf("0\n");

                continue;

            }

            LL s = -c/b;

            if(s>=y1 && s<=y2)

                printf("%lld\n",x2-x1+);

            else

                printf("0\n");

            continue;

        }

        if(b==)

        {

            if(c%a!=)

            {

                printf("0\n");

                continue;

            }

            LL s = -c/a;

            if(s>=x1 && s<=x2)

                printf("%lld\n",y2-y1+);

            else

                printf("0\n");

            continue;

        }

        LL g = ex_gcd(a,b,x,y);

        if(c%g!=)

        {

            printf("0\n");

            continue;

        }

        if(sign(g) * sign(b) <) swap(x1,x2);

        LL l1 = ceil(b, g*x1 + c*x);

        LL l2 = floor(b, g*x2 + c*x);

        if(sign(-a) * sign(g) <) swap(y1,y2);

        LL r1 = ceil(-a,g * y1 + c*y);

        LL r2 = floor(-a,g*y2 + c*y);

        l1 = max(l1,r1);

        r1 = min(l2,r2);

        if(l1>r1) printf("0\n");

        else

            printf("%lld\n",r1-l1 +);

    }

    return ;

}