/* Author haleyk10198 */
/* §@ªÌ:  haleyk10198 */
#include <bits/stdc++.h>

#define MOD 1000000007
#define LINF (1LL<<60)
#define INF 2147483647
#define PI 3.1415926535897932384626433
#define ll long long
#define pii pair<int,int>
#define mp(x,y) make_pair((x),(y))

using namespace std;

string itos(int x){
    stringstream ss;
    ss<<x;
    return ss.str();
}

int t;

int main(){
    freopen("C-large.in","r",stdin);
    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin>>t;
    for(int i=1;i<=t;i++){
        int n,d;
        ll res=0;
        cin>>n>>d;
        for(int i=1;i*d<=n;i++){
            int lv=n/i;
            lv-=lv%d;
            if(!lv)
                continue;
            int rem=n-lv*i;
            int m1=rem,m2=(rem+1)/2;
            int l=max(1,i-m1);
            int r=max(0,i-m2);
            res+=r-l+1;
            if(d==1&&--lv>0){
                rem=n-lv*i;
                m1=rem,m2=(rem+1)/2;
                l=max(1,i-m1);
                r=max(0,i-m2);
                res+=r-l+1;
            }
        }
        printf("Case #%d: %I64d\n",i,res);
    }
    return 0;
}