#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

struct node{

	static const int mo=100007;

	int a[100010],v[100010];

	node() {memset(a,-1,sizeof(a));}

	int find(int val){

		int pos=(val%mo+mo)%mo;

		while ((a[pos]!=val)&&(a[pos]!=-1)) pos=(pos+1)%mo;

		return pos;

	}

	void insert(int val,int x){

		int pos=find(val);

		if ((a[pos]==-1)||(a[pos]==val)){

			a[pos]=val;

			v[pos]=x;

		}

	}

	int get(int val){

		int pos=find(val);

		return a[pos]==val?v[pos]:-1;

	}

	void clear() {memset(a,-1,sizeof(a));}

}hash;

int T,L;

inline int work1(int a,int b,int n){

	long long t=a,ans=1;

	while (b){

		if (b%2==1) ans=(ans*t)%n;

		b=b/2;

		t=(t*t)%n;

	}

	return (int)ans;

}

inline int exgcd(int a,int b,int &x,int &y){

	if (b==0){

		x=1; y=0; return a;

	}else{

		int r=exgcd(b,a%b,x,y);

		int t=y;

		y=x-a/b*y;

		x=t;

		return r;

	}

}

inline void work2(int a,int b,int n){

	int x,y;

	int d=exgcd(a,n,x,y);

	if (b%d) puts("Orz, I cannot find x!\n");

	else printf("%d\n",(int)((((long long)x*b/d%n)+n)%n));

}

inline void work3(int a,int b,int n){

	if ((a%n==0)&&(b!=0)) {puts("Orz, I cannot find x!\n"); return;}

	hash.clear();

	int m=ceil(sqrt(n));

	long long t=b%n;

	for(int i=0;i<=m;++i){

		hash.insert((int)t,i);

		t=(t*a)%n;

	}

	int s=work1(a,m,n); t=s;

	for(int i=1;i<=m;++i){

		int v=hash.get((int)t);

		if (v!=-1) {printf("%d\n",i*m-v); return;}

		t=(t*s)%n;

	}

	puts("Orz, I cannot find x!\n");

}

int main(){

	scanf("%d %d\n",&T,&L);

	int y,z,p,a,b;

	switch (L){

		case 1:

			while (T--){

				scanf("%d %d %d\n",&y,&z,&p);

				printf("%d\n",work1(y,z,p));

			}

		break;

		case 2:

			while (T--){

				scanf("%d %d %d\n",&y,&z,&p);

				work2(y,z,p);

			}

		break;

		case 3:

			while (T--){

				scanf("%d %d %d\n",&y,&z,&p);

				work3(y,z,p);

			}

		break;

	}

	return 0;

}