#include<iostream>#include<stdio.h>using namespace std;int a[ 45100 ],b[ 45100 ];int mod(int a,int b,int c){ int z=1; while( b ) { if( b%2 )z = ( z * a ) % c; b/=2; a = ( a * a ) % c; } return z;}int main(){ int T,m,n,ans; scanf("%d",&T); while( T-- ) { scanf("%d%d",&m,&n); for(int i=0;i<n;i++) { scanf("%d%d",&a[i],&b[i]);a[i] %= m; } ans = 0; for(int i=0;i<n;i++) { ans = ( ans + mod(a[i],b[i],m) )% m; } printf("%dn",ans); }}
