int pa[1d6],pn;
ll t,a,p;
{
	pn=Prime(5d6,pa);
	rd(t);
	rep(t){
		rd(a,p);
		if(*lower_bound(pa,pa+pn,p)==p){
			wt(a%p?1:0);
		}else{
			wt(-1);
		}
	}
}