Start: Jun, 28, 2019 08:42:00
2019杭州师范大学第一届程序设计竞赛新生赛
End: Jun, 28, 2019 11:42:00
Time elapsed:
Time remaining:

Problem_ID: D
Result: Accepted
Time: 81ms
Memory: 1092kB
In contest: 1276

#include<stdio.h>
int gcd(int m,int n)
{
	int temp;
	if(n>m)
	{
		temp=n;
		n=m;
		m=temp;
	}
	if(m%n==0)
		return n;
	else
		return gcd(m-n,n);
}
int main()
{
	int n,q,si,ti;
	scanf("%d%d",&n,&q);
	while(q--)
	{
		scanf("%d%d",&si,&ti);
		if(gcd(si,ti)==1)
			printf("1\n");
		else
			printf("2\n");
	}
}