ll@n,@m,@p,@q;
rep(q){
	ll@x,@f;
	wt(x%p?m/p+((f*powmod(x,p-2,p)+p-1)%p<m%p):f?0:m);
}