#include using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x enumpr(ll n) { set V; for(ll i=2;i*i<=n;i++) while(n%i==0) V.insert(i),n/=i; if(n>1) V.insert(n); return V; } ll ext_gcd(ll p,ll q,ll& x, ll& y) { // get px+qy=gcd(p,q) if(q==0) return x=1,y=0,p; ll g=ext_gcd(q,p%q,y,x); y-=p/q*x; return g; } ll inv(ll p,ll q) { // return (1/p)%q ( p,q is co-prime) ll xx,yy; ll g=ext_gcd(p,q,xx,yy); if(xx<0) xx+=q, yy-=p; return xx; } ll CRT_garner(vector > V, ll mo=1000000007) { int i,j,k,l,r,x,y; string s; int N=V.size(); set P; vector num; FOR(i,N) { set S=enumpr(V[i].second); FORR(r,S) P.insert(r); } num=vector(N,0); FORR(r,P) { y=0; FOR(x,N) { num[x]=1; j=V[x].second; while(j%r==0) j/=r, num[x]*=r; if(num[y] > V2; FOR(x,N) if(V[x].second>1) V2.emplace_back(V[x].second,V[x].first); sort(V2.begin(),V2.end()); V=V2; N=V.size(); // garner FOR(y,N) FOR(x,y) { ll k=V[y].second-V[x].second; if(k<0) k+=V[y].first; V[y].second = k*inv(V[x].first,V[y].first)%V[y].first; } ll ret=0; for(x=N-1;x>=0;x--) ret = (ret*V[x].first+V[x].second)%mo; return ret; } void solve() { int N,i,x,y; vector > V; cin>>N; FOR(i,N) { cin>>x>>y; V.emplace_back(x,y); } cout<