#include <iostream> usingnamespace std; int main() { long z, m, h, a, b, tmp,e; cin>>z; while (z--) { cin>>m>>h; tmp =0; for (long i =0; i < h; ++i) { cin>>a>>b; __int64 d =1; long nlen =0; short Bin[34]={0}; while (b%2!= b) { Bin[nlen++] = b%2; b >>=1; } Bin[nlen] = b; d=a;e=1; for (long i =0; i <=nlen; i++) { if (Bin[i] ==1) { e = (e*d)%m; } d = (d*d)%m; } tmp+=e; } cout<<(m+tmp%m)%m<<endl; } return0; }