#include <cstdio>#include <cstring>#include <algorithm>#include <algorithm>using namespace std;typedef long long LL;LL fac[ 100000 ], pf;LL gcd( LL a, LL b ){    LL x, y, z;    if( a > b ) x = a, y = b;    else        x = b, y = a;    while( y )    {        z = x % y;        x = y;        y = z;    }    return x;}LL mul( LL a, LL b, LL c ){    LL res = 0;    a %= c;    while( b )    {        if( b & 1 )        {            res += a;            if( res >= c ) res -= c;        }        a <<= 1;        if( a >= c ) a -= c;        b >>= 1;    }    return res;}LL fast_mod( LL a, LL b, LL c ){    LL res = 1;    while( b )     {        if( b & 1 )    res = mul( res, a, c );        a = mul( a, a, c );        b >>= 1;    }    return res;}LL euler( LL x )    //得到欧拉函数phi {    LL res = x, i;    for( i = 2; i * i <= x; ++i )    {        if( x % i == 0 )        {            x /= i;            res = res - res / i;            while( x % i == 0 )                x /= i;        }    }    if( x > 1 )        res = res - res / x;    return res;}void factor( LL x )    //得到x的所有约数 {    pf = 0;    for( LL i = 2; i * i <= x; ++i )    {        if( x % i == 0 )        {            fac[ pf++ ] = i;            fac[ pf++ ] = x / i;        }    }    fac[pf++] = x;}int main(){    LL cas = 1, p, q, d, start, eul, id;    while( ~scanf( "%lld %*c %lld", &p, &q ) )    {        printf( "Case #%d: ", cas++ );        if( p == 0 )        {            puts( "1,1" );            continue;        }        d = gcd( p, q );        p /= d;        q /= d;        start = 1;        while( (q & 1) == 0 )         {            start++;            q >>= 1;        }        eul = euler( q );        factor( eul );        sort( fac, fac + pf );                 for( id = 0; id < pf; ++id )            if( fast_mod( 2, fac[id], q ) == 1 )                    break;        printf( "%lld,%lld\n", start, fac[id] );    }    return 0;}