#define ssh(x)<x>
#include ssh(bits/stdc++.h)
#define rfor(x...)for(register x)
#define rep(i,l,r)rfor(ll i=l;i<=r;i++)
#define per(i,l,r)rfor(ll i=l;i>=r;i--)
#define ref(i,l,r)rfor(ll i=l;i<r;i++)
#define rev(i,u,v)rfor(ll i=head[u],v;v=to[i],i;i=next[i])
#define rej(i,s)rfor(ll i=s;i;i=(i-1)&(s))
#define red(i,n)rfor(ll i=n;i;i>>=1)
#define IO(x...)*#x&&freopen(#x".in","r",stdin)&&freopen(#x".out","w",stdout),gc=fgc,pc=fpc,atexit(fout)
typedef long long ll;
typedef const ll cll;
typedef unsigned long long ull;
cll N=1e6+7,mod=3e9+7,iz=1<<21,oz=1<<22;
typedef ll aN[N];
char is[iz],*i1=is,*i2=is,os[oz],*o1=os,*o2=os+oz;
int fgc(){
    return i1==i2&&is==(i2=is+fread(i1=is,1,iz,stdin))?-1:*i1++;
}
void fout(){
    fwrite(os,o1-os,1,stdout),o1=os;
}
int fpc(int c){
    if(o1==o2)fout();
    return*o1++=c;
}
int(*gc)()=getchar,(*pc)(int)=putchar,wt[126];
int readchar(int l=33,int r=126){
    if(l>r)std::swap(l,r);
    int c=gc();
    for(;c<l||c>r;c=gc());
    return c;
}
ll readll(){
   ll x=0,w=1;
   int c=gc();
   for(;c<48||c>57;c=gc())c-45||(w=-w);
   for(;c>47&&c<58;c=gc())x=x*10+c-48;
   return x*w;
}
void writell(cll u,int c=32){
    int t=0;
    rfor(ull n=u<0?pc(45),0ull-u:u;n;n/=10)wt[++t]=n%10^48;
    for(t||pc(48);t;)pc(wt[t--]);
    c&&pc(c);
}
int mygets(char*s,int c=0){
    char*t=s+1;
    while((*s=gc())<33);
    while((*t=gc())>32)t++;
    c&&(*t++=c),*t=0;
    return t-s;
}
int myputs(const char*s,int c=10){
    const char*t=s;
    while(*t)pc(*t++);
    c&&pc(c);
    return t-s+(c!=0);
}
typedef long double ld;
ll r;
ld s;
static inline ll gcd(ll a,ll b){
    while(b){
        cll t=a/b,lb=b;
        b=a-t*b,a=lb;
    }
    return a;
}
struct node{
    ll a,b,c;
    ld v()const{
        return(a*s+b)/c;
    }
    node operator/(cll n)const{
        return(node){a,b,c*n};
    }
    node&calc(cll n){
        return n&1?b=c*n+c-b,a=-a:b-=c*n,*this;
    }
    node&operator-=(cll n){
        return b-=c*n,*this;
    }
    void inv(){
        cll h=a*a*r-b*b;
        if(h%c==0)b=-b,c=h/c;
        else a*=c,b*=-c,c=h;
    }
};
static inline ll get(cll h,ll u){
    return h?-u:u;
}
static inline ll getans(node k,ll n){
    ll res=0,h=0;
    while(n){
        cll x=k.v();
        k.calc(x),h^=x&1;
        cll m=n*k.v();
        k.inv();
        ld kv=k.v();
        cll l=(m&~1)*kv;
        if(m&1){
            cll z=m*kv;
            res+=get(h,z-n+z-l);
        }else res+=get(h,n-l);
        k-=kv,n=(m&~1)*k.v(),k.inv();
    }
    return res;
}
void calc(){
    cll n=readll(),r=::r=readll(),s=::s=sqrtl(r);
    if(s*s==r)return writell(s&1?n&1?-1:0:n,10);
    writell(getans((node){1,0,1},n),10);
}
int main(){
    IO();
    //gc=getchar;
    cll T=readll();
    rep(i,1,T)calc();
    return 0;
}
/*
3
806045030 886
683448424 6915
959503440 8335
*/