ll@t;
rep(t){
	ll@n,@k;
	redo:;
	if(n==k){
		wt(-1);
		continue;
	}
	for(long i=n/+k;i*i<=n;++i){
		if(n%i==0){
			--n;
			goto redo;
		}
	}
	wt(n);
}