#include <iostream>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while (T--){
        long long n,k;
        cin>>n>>k;
        if (n==1&&k==0){
            cout<<1<<endl;
        }else if(k==0){
            cout<<1<<endl;
        }else if(k==1){
            cout<<(n+1)/2<<endl;
        }else{
            cout<<(n/k-n/(k+1))%(k+1)<<endl;
        }
    }
    return 0;
}