#include<iostream>
using namespace std;
 
void solve(int limit, int div){
    long long res = 0;
    for(int i = 1; i < div; i++){ //duyệt qua tất cả các khả năng dư khi chia cho div
        if((1ll*i*i) % div == 1){
            long long maxVal = i + 1ll * div * (limit / div);//số lớn nhất mà trong khoảng limit có phần dư là i
            if(maxVal > limit) maxVal -= div; //chắc chắn số đó không quá limit
            res += (maxVal-i)/div + 1;//đếm các số có phần dư là i
        }
    }
    cout << res << '\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T; cin >> T;
    while(T--){
        int a, b;
        cin >> a >> b;
        solve(a, b);
    }
    return 0;
}

I2luY2x1ZGU8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIHNvbHZlKGludCBsaW1pdCwgaW50IGRpdil7CiAgICBsb25nIGxvbmcgcmVzID0gMDsKICAgIGZvcihpbnQgaSA9IDE7IGkgPCBkaXY7IGkrKyl7IC8vZHV54buHdCBxdWEgdOG6pXQgY+G6oyBjw6FjIGto4bqjIG7Eg25nIGTGsCBraGkgY2hpYSBjaG8gZGl2CiAgICAgICAgaWYoKDFsbCppKmkpICUgZGl2ID09IDEpewogICAgICAgICAgICBsb25nIGxvbmcgbWF4VmFsID0gaSArIDFsbCAqIGRpdiAqIChsaW1pdCAvIGRpdik7Ly9z4buRIGzhu5tuIG5o4bqldCBtw6AgdHJvbmcga2hv4bqjbmcgbGltaXQgY8OzIHBo4bqnbiBkxrAgbMOgIGkKICAgICAgICAgICAgaWYobWF4VmFsID4gbGltaXQpIG1heFZhbCAtPSBkaXY7IC8vY2jhuq9jIGNo4bqvbiBz4buRIMSRw7Mga2jDtG5nIHF1w6EgbGltaXQKICAgICAgICAgICAgcmVzICs9IChtYXhWYWwtaSkvZGl2ICsgMTsvL8SR4bq/bSBjw6FjIHPhu5EgY8OzIHBo4bqnbiBkxrAgbMOgIGkKICAgICAgICB9CiAgICB9CiAgICBjb3V0IDw8IHJlcyA8PCAnXG4nOwp9CmludCBtYWluKCl7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoMCk7CiAgICBpbnQgVDsgY2luID4+IFQ7CiAgICB3aGlsZShULS0pewogICAgICAgIGludCBhLCBiOwogICAgICAgIGNpbiA+PiBhID4+IGI7CiAgICAgICAgc29sdmUoYSwgYik7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==