#include<iostream>
#define LL long long
using namespace std;
//快速幂算法
LL pow(LL a,LL b,int m){
LL r=,base=a;
while(b!=){
if(b&)
r=r*base%m;//同余模公式
base=base*base%m;//同余模公式
b>>=;
}
return r;
}
int main(){
int n,r,m;
cin>>n;
while(n--){
cin>>r>>m;
LL x,y,sum=;
for(int i=;i<m;i++){
cin>>x>>y;
sum+=pow(x,y,r);
}
cout<<sum%r<<endl;//同余模公式
}
return ;
}
快速幂顾名思义，就是快速算某个数的多少次幂。其时间复杂度为O（log2N），与朴素的O（N）相比效率有了极大的提高。
以下以求a的b次方来介绍[1]
把b转换成二进制数。
该二进制数第i位的权为
例如
11的二进制是1011
11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1
因此，我们将a¹¹转化为算
了解到了这个便有了思路，
在计算幂的过程中，为了保证不溢出，使用同余模公式：
(a+b)%m=(a%m+b%m)%m;
(axb)%m=(a%mxb%m)%m;