#include <bits/stdc++.h>

#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((vlong)(x).size())
#define NORM(x) if(x>=mod)x-=mod;

using namespace std;

typedef long long vlong;

#define SIZE 100001

int bit[SIZE+10];

void bitClear( int n ) {
    FOR(i,1,n+2) {
        bit[i] = 0;
    }
}
void bitInsert ( int from, int what ) {
    from++; ///Handle 0

    for ( int i = from; i <= SIZE; i += i & (-i) ) {
        bit[i] += what;
    }
}

int bitQuery ( int at ) {
    at++; ///Handle 0

    int res = 0;
    for ( int i = at; i > 0; i -= i & -i ) {
        res += bit[i];
    }
    return res;
}



int main () {

    int kase, cnt = 0;
    scanf ( "%d", &kase );

    while ( kase-- ) {
        int n, k;
        scanf ( "%d %d", &n, &k );

        bitClear(k); ///Clear BIT

        vlong total = 0;
        vlong res = 0;
        ROF(i,1,n) {
            total++; ///Total number of "c" available

            int x = ( i * i * i ) % k;
            bitInsert( x, 1 ); ///Insert another "c"

            res += ( i / k ) * total; ///This many "a" segment can handle any "c"


            int r = i % k;
            int b = ( i * i ) % k;

            if ( r > 0 ) { ///These parts of "a" were not used

                int from = 1 + b; ///c >= 1 + b
                int to = r + b; ///c <= r + b

                if ( from >= k ) { ///In case both from and to exceed k
                    from -= k;
                    to -= k;
                }

                int seg = 0;
                if ( to < k ) { ///Continuous
                    seg = bitQuery(to);
                    seg -= bitQuery(from-1);
                }
                else { ///Wraps around
                    seg = bitQuery(k-1); ///from - end
                    seg -= bitQuery(from-1);

                    seg += bitQuery(to%k); ///0 - to
                }
                res += seg;
            }
        }

        printf ( "Case %d: %lld\n", ++cnt, res );
    }

    return 0;
}