#include<stdio.h>
#include"guess.h"
using namespace std;
typedef long long LL;
void init(int subtask_id,int T){;}
struct node{
	LL l,r;//x∈[0,r]
};
LL fP,fn;
inline LL getchu0(LL x,LL y){return x/y;}
inline LL getchu1(LL x,LL y){
	if(!x)return 0;
	else return (x-1)/y+1;
}
inline node getnode(LL l,LL r){//在乘n意义下问题都不大 
	node b;
	b.l=getchu1(l,fn);b.r=getchu0(r,fn);
	return b;
} 
int tim[10],top;
node sta[50];int len[50];
long long solve(long long P,int n){
	fP=P;fn=n;
	LL x=(n-P%n)%n,xx;//表示一次-P对模数带来的影响 
	xx=x;
	tim[0]=0;for(int i=1;i<n;i++)tim[x]=i,x=(x+xx)%n;
	LL cha=1;top=0;
	while(cha<P){
		top++;
		LL x=query(0)^2;//查询得到新的seed
		LL fuc=tim[x];len[top]=fuc;
		LL l=fuc*P,r=(fuc+1)*P-1;
		sta[top]=getnode(l,r);
		cha=cha*n;
	}
	for(int i=top-1;i>=1;i--){
		LL l=sta[i+1].l+len[i]*P,r=sta[i+1].r+len[i]*P;
		sta[i]=getnode(l,r);
	}
	LL seed=sta[1].l;
	for(int i=1;i<=top;i++)seed=seed*n%P;
	LL l=1,r=(LL)1e18,mid,ans;
	while(l<=r){
		seed=seed*n%P;LL val=seed%n;
		mid=(l+r)>>1;LL type=(query(mid)^val);
		if(type==1)return mid;
		else if(type==0)ans=mid,r=mid-1;//ans<mid
		else l=mid+1;//ans>mid
	}
	return ans;
}