poj1995---Raising Modulo Numbers

//long long 如果输入不使用%lld的话，如果输入数据超过int范围会wa
//(a+b)%c=(a%c+b%c)%c;
//(a*b)%c=[(a%c)*(b%c)]%c
//(a^b)%c=(a%c)^b%c---幂是多次乘法
//(a*b)%c=(a%c)*b%c
//有详细证明：https://blog.csdn.net/qq_36285879/article/details/53284431
#include<cstdio>
using namespace std;
int z;
int m,h;
long long ans,a,b;
long long binaryPow(long long a,long long b, int m ){
    long long ans=1;
    while(b>0){
        if(b&1){
            ans=ans*a%m;//(a*b)%c=(a%c)*b%c
        }
        a=a*a%m;//(a%c)
        b=b>>1;
    }
    return ans;
}
int main(){
    scanf("%d",&z);
    while(z--){
        scanf("%d%d",&m,&h);
        long long ans=0;
        for(int i=0;i<h;i++){
            scanf("%lld%lld",&a,&b);
            ans+=binaryPow(a,b,m);
        }
        ans=ans%m;
        printf("%lld\n",ans);


    }
    return 0;
}