> #include <cstdio>
> using namespace std;
> int cas,m,n;
> long long a,b,ans;
> 
> long long js(long long a,long long b)
> {
> 	if(b==0)return 1;
> 	if(b==1)return a;
> 	long long res=js(a,b/2);
> 	if(b%2==0)return res*res%m;
> 	else return res*res*a%m;
> }
> 
> int main()
> {
> 	scanf("%d",&cas);
> 	while(cas--)
> 	{
> 		scanf("%d%d",&m,&n);
> 		ans=0;
> 		while(n--)
> 		{
> 			scanf("%I64d%I64d",&a,&b);
> 			a=a%m;
> 			ans=(ans+js(a,b))%m;
> 		}
> 		printf("%I64d\n",ans);
> 	}
> 	return 0;
> }