#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==