#include <iostream>
using namespace std;
int a,p;
long long  mod2(int k)
{
	int i;
	long long m;
	m = a%p;
	for(i=0;i<k;i++)
		m = (m*m)%p;
	return m;
}
int done()
{
	int k,q=p/2;
	long long m=1;
	for(k=0;k<32;k++)
		if(((1<<k)&q)>0)
			m = m*mod2(k)%p;
	if(m==1)
		return 1;
	else
		return -1;
}
int main()
{
	int t,tt;
	scanf("%d",&tt);
	for(t=1;t<=tt;t++)
	{
		scanf("%d%d",&a,&p);
		if(a<0&&(p-3)%4==0)
		{
			a=-a;
		   printf("Scenario #%d:\n%d\n\n",t,(-1)*done());
		}
		else 
		{
			if(a<0&&(p-1)%4==0) a=-a;
			printf("Scenario #%d:\n%d\n\n",t,done());
		}

	}
	return 0;
}
...可不可以讲一下他的计算思路。。看不懂啊