#include <bits/stdc++.h>
using namespace std;
#define MAX 10000000
vector <int> primes;
long long int GCD( long long int a, long long int b ) {
    if( b == 0 ) return a;
    if( a < b ) swap( a, b );
    int r = a % b;
    return GCD( b, r );
}
int prime[MAX];
int setBit( int n, int position ) {
    n = n | ( 1 << position );
    return n;
}
bool checkBit(int n, int position) {
    return n & ( 1 << position );
}
void primeGenerator( int n ) {
    int x = sqrt( n );
    primes.push_back(2);
    prime[0] = setBit( prime[0], 0 );
    prime[0] = setBit( prime[0], 1 );
    for( int i = 4; i <= n; i += 2 )
       prime[ i >> 5 ] = setBit( prime[ i >> 5 ], i & 31 );
    for( int i = 3; i <= x; i += 2 ) {
       if( !checkBit( prime[ i >> 5 ], i & 31 ) ) {
            primes.push_back(i);
            for( int j = i+i; j <= n; j += i )
                prime[ j >> 5 ] = setBit( prime[ j >> 5 ], j & 31 );
        }
    }
    return;
}
int main() {
    primeGenerator(10000000);
    int T;

    scanf("%d", &T);
    int cs;

    for (cs=1; cs<=T; cs++) {
        vector <int> ber;
        vector <int> aer;
        long long int a, b, bb;
        scanf("%lld %lld", &a, &b);
        bb = b;
        long long int i;
        for (i=0; primes[i]*primes[i] <= b; i++) {
            if (b % primes[i] == 0) {
                while (b%primes[i] == 0) {
                    ber.push_back(primes[i]);
                    b/=primes[i];
                }
            }
        }
        if (b>=2) ber.push_back(b);
        for (i=0; primes[i]*primes[i] <= a; i++) {
            if (a % primes[i] == 0) {
                while (a%primes[i] == 0) {
                    aer.push_back(primes[i]);
                    a/=primes[i];
                }
            }
        }
        if (a>=2) aer.push_back(a);
        long long int  gcd = 0, cnt=0, j =0, k = 0, xx = aer[0];
        i=0;
        while (aer[i] == xx && i<aer.size()) {
            i++;
            gcd++;
        }
        for (; i<aer.size(); i++) {
            xx = aer[i];
            cnt =0;
            while (aer[i] == xx && i<aer.size()) {
                i++;
                cnt++;
            }
            gcd = GCD(cnt, gcd);
        }

        for (i=0; primes[i]*primes[i] <= gcd; i++) {
            if (gcd % primes[i] == 0) {
                while (gcd%primes[i] == 0) {
                    ber.push_back(primes[i]);
                    gcd/=primes[i];
                }
            }
        }
        if (gcd>=2) ber.push_back(gcd);
        long long int ans = 1;

        sort(ber.begin(), ber.end());

        for (i=0; i<ber.size(); ) {
            xx = ber[i];
            cnt =0;
            while (ber[i] == xx && i<ber.size()) {
                i++;
                cnt++;
            }
            ans*= (cnt+1);
        }

        printf("Case %d: %lld\n",cs, ans-1);
    }
    return 0;
}