#include<fstream>
#include<cmath>
using namespace std;
ifstream cin("progresie.in");
ofstream cout("progresie.out");
int main()
{
    short t;
    for(cin>>t;t--;) {
        short n;
        int r;
        cin>>n>>r;
        long long k=1LL*(r*n-r+1)*(r*n-r+1)-r*n+r;
        for(long long i=1,j=2;i<=k;i+=j,j+=2) {
            bool o=1;
            for(long long l=i;l<=i+r*n-r;l+=r) {
                long long r=sqrt(l);
                if(r*r!=l&&(r+1)*(r+1)-r>l)
                    o=0;
            }
            if(o) {
                cout<<i<<'\n';
                break;
            }
        }
    }
    return 0;
}