#include<stdio.h>
int main()
{
	int t,p;
	long long n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%lld",&p,&n);
		long long  pre1=1,pre2=1,now;
		if(n<=2){
			printf("1\n");
			continue;
		}
		int xhj;//循环节长度 
		for(int i=3;i<=p*p+2;i++){//寻找循环节 
			now=(pre1+pre2)%p;   //计算斐波那契数列 
			if(now==1&&pre2==1){    //如果有两项是1 1，则找到循环节 
				xhj=i-2;
				break;
			}
			pre1=pre2;
			pre2=now;
		}
		n=(n-1)%xhj+1;//除以循环节 
		pre1=pre2=1;
		for(int i=3;i<=n;i++){  //找到答案 
			now=(pre1+pre2)%p;
			pre1=pre2;
			pre2=now;
		}
		printf("%lld\n",now);
		
	} 
}