#include <iostream>#include <cstdio>using namespace std;int quick(int a,int b,int m){	int ans=1;	a%=m;	while(b){		if(b&1){			ans=(ans*a)%m;			b--;		}		a=(a*a)%m;		b/=2;	}	return ans;}int main(){	int t;	scanf("%d",&t);	int m,n; int ans,a,b;	while(t--){		ans=0;		scanf("%d",&m);		scanf("%d",&n);		for(int i=0;i<n;i++){			scanf("%d%d",&a,&b);			ans=(ans+quick(a,b,m))%m;		}		printf("%d\n",ans%m);	}	return 0;}