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: 74ms
Memory: 1712kB
In contest: 1276

#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
using namespace std;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int n,q;
    int u,v;
    scanf("%d%d",&n,&q);
    for(int i=0;i<q;++i)
    {
        scanf("%d%d",&u,&v);
        if(gcd(u,v)==1)
            puts("1");
        else
            puts("2");
    }
    return 0;
}