include[HTML_REMOVED]
using namespace std;
const int N=1e7+10;
int t;
int a,b,m,h;
int mh(int a,int b)
{
int p=1%m;
while(b)
{
if(b&1) p=p*1ll*a%m;
a=a*1ll*a%m;
b>>=1;
}
return p;
}
int main()
{
cin>>t;
while(t--){
cin>>m;
cin>>h;
int r=0;
while(h--){
cin>>a>>b;
r=(r+mh(a,b))%m;
}
cout<<r<<endl;
}
return 0;
}