#include #include #include #include #define REP(i,a,b) for(i=a;iintLmfFlow[i][j]) s=intLmfFlow[i][j]; t=intsListMaxFlowFlow(k,ed,s); if(!t) continue; ret+=t; lim-=t; ji=intLmfInv[i][j]; intLmfFlow[i][j]-=t; intLmfFlow[k][ji]+=t; if(!lim) break; } if(lim) intLmfLevel[i]=-1; return ret; } ll intsListMaxFlow(int n,int st,int ed){ ll ret=0; for(;;){ intListMaxFlowLevelize(n,st,ed); if(intLmfLevel[ed]==-1) break; ret += intsListMaxFlowFlow(st,ed,LL_INF); } return ret; } void intListMaxFlowAllocInit(int s){ int i; rep(i,INT_LIST_MAX_FLOW_NODE){ intLmfEdgeMemory[i]=s; intLmfEdge[i] = (int*) malloc(s*sizeof(int)); intLmfFlow[i] = (int*) malloc(s*sizeof(int)); intLmfInv[i] = (int*) malloc(s*sizeof(int)); } } void intListMaxFlowAllocPerInit(int i,int s){ intLmfEdgeMemory[i]=s; intLmfEdge[i] = (int*) malloc(s*sizeof(int)); intLmfFlow[i] = (int*) malloc(s*sizeof(int)); intLmfInv[i] = (int*) malloc(s*sizeof(int)); } void intListMaxFlowAlloc(int i,int s){ if(intLmfEdgeMemory[i]>=s) return; intLmfEdgeMemory[i]=s; free(intLmfEdge[i]); free(intLmfFlow[i]); free(intLmfInv[i]); intLmfEdge[i] = (int*) malloc(s*sizeof(int)); intLmfFlow[i] = (int*) malloc(s*sizeof(int)); intLmfInv[i] = (int*) malloc(s*sizeof(int)); } void intListMaxFlowEdgeInitAdv(int n){ int i; rep(i,n) intLmfEdgeSize[i]=0; } void intListMaxFlowEdgeInit(){ int i; rep(i,INT_LIST_MAX_FLOW_NODE) intLmfEdgeSize[i]=0; } void intListMaxFlowEdgeAdd(int n1,int n2,int f1,int f2){ int s1=intLmfEdgeSize[n1]++, s2=intLmfEdgeSize[n2]++; intLmfEdge[n1][s1]=n2; intLmfEdge[n2][s2]=n1; intLmfFlow[n1][s1]=f1; intLmfFlow[n2][s2]=f2; intLmfInv[n1][s1]=s2; intLmfInv[n2][s2]=s1; } /* END : max flow (Dinic) */ /* START : primality test (Miller-Rabin) */ int ullNumberOfLeadingZerosTable[256]={8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; int ullNumberOfLeadingZeros(ull x){ int res=56; unsigned xl=x, xh=x>>32; if(xh) res -= 32, xl = xh; if(xl&0xffff0000U) res -= 16, xl >>= 16; if(xl&0x0000ff00U) res -= 8, xl >>= 8; return res + ullNumberOfLeadingZerosTable[xl]; } ull ullMultipleMod(ull x, ull y, ull m){ int k,loop=2; ull xlo,xhi,ylo,yhi,rlo,rhi,d1,d2,a,q,r,mask=0xffffffffULL; if(m<=mask) return (x*y)%m; xlo=(x&mask); xhi=(x>>32); ylo=(y&mask); yhi=(y>>32); rhi=xhi*yhi; rlo=xlo*ylo; a=(rlo>>32)+xhi*ylo; rhi+=(a>>32); a&=mask; a+=xlo*yhi; rhi+=(a>>32); rlo = (rlo&mask) | ((a&mask)<<32); k = ullNumberOfLeadingZeros(m); rhi = (rhi<>(64-k)); rlo<<=k; m<<=k; d1=(m>>32); d2=(m&mask); while(loop--){ r = rhi/d1*d2; rhi = ( (rhi%d1 << 32) | (rlo>>32) ); rlo = ( (rlo&mask) << 32 ); if(rhim) rhi+=m; } return rhi>>k; } ull ullPowMod(ull x, ull k, ull m){ ull res; if(k==0) return 1; res = ullPowMod(x,k/2,m); res = ullMultipleMod(res,res,m); if(k%2) res = ullMultipleMod(res,x,m); return res; } ull unsignedMillerRabinSuspectPow(int a, unsigned k, unsigned n){ ull p=1; unsigned bit; for (bit=0x80000000U;bit;bit>>=1) { if(p>1) p=(p*p)%n; if(k&bit) p=(p*a)%n; } return p; } int unsignedMillerRabinSuspect(int b, unsigned n){ unsigned i,t=0,u=n-1; ull now, next; while(!(u&1)) t++, u>>=1; now = unsignedMillerRabinSuspectPow(b, u, n); for(i=1;i<=t;i++){ next=(now*now)%n; if(next==1 && now!=1 && now!=n-1) return 0; now=next; } return next==1; } int unsignedMillerRabin(unsigned n){ if(n<=1)return 0; if(n<=3)return 1; if(!(n&1))return 0; if(!unsignedMillerRabinSuspect(2,n)) return 0; if(n<=1000000){ if(!unsignedMillerRabinSuspect(3,n)) return 0; } else { if(!unsignedMillerRabinSuspect(7,n)) return 0; if(!unsignedMillerRabinSuspect(61,n)) return 0; } return 1; } ull ullMillerRabinSuspectPow(ull a, ull k, ull n){ ull p=1, bit; for (bit=0x8000000000000000ULL;bit;bit>>=1) { if(p>1) p=ullMultipleMod(p,p,n); if(k&bit) p=ullMultipleMod(p,a,n); } return p; } int ullMillerRabinSuspect(ull b, ull n){ ull i, t=0, u=n-1, now, next; while(!(u&1)) t++, u>>=1; now = ullMillerRabinSuspectPow(b, u, n); for(i=1;i<=t;i++){ next=ullMultipleMod(now,now,n); if(next==1 && now!=1 && now!=n-1) return 0; now=next; } return now==1; } int ullMillerRabin(ull n){ int i,lim; if(n<(1ULL<<32)) return unsignedMillerRabin(n); if(!(n&1)) return 0; if(n < 341550071728321ULL) lim=17; else lim=29; if(!ullMillerRabinSuspect(2,n)) return 0; for(i=3;i<=lim;i+=2) if(!ullMillerRabinSuspect(i,n)) return 0; return 1; } /* END : primality test (Miller-Rabin) */ int main(){ int i,j,k,loop,tests; int N; ll num[510]; int cnt[510]; int edge[510][510]; int color[510], st[510], st_size; ll p, flow, sum, flow2, res; int node, n1, n2, S, T; int nn[510]; char *First = "Bran", *Second = "Tyrion"; intListMaxFlowAllocInit(1002); tests = 1; while(tests--){ assert( scanf("%d",&N)==1 ); assert( 1<=N && N<=500 ); rep(i,N) assert( scanf("%lld%d",num+i,cnt+i)==2 ); rep(i,N) assert( 1<=num[i] && num[i]<=1000000000000000000LL && 1<=cnt[i] && cnt[i]<=1000000000 ); /* sort such as num[0] > num[1] > num[2] > ... */ rep(i,N) REP(j,1,N) if(num[j-1] < num[j]){ p = num[j-1]; num[j-1] = num[j]; num[j] = p; k = cnt[j-1]; cnt[j-1] = cnt[j]; cnt[j] = k; } REP(i,1,N) assert( num[i-1] > num[i] ); sum = 0; rep(i,N) sum += cnt[i]; /* create graph */ rep(i,N) edge[i][i] = 0; rep(i,N) REP(j,i+1,N){ edge[i][j] = edge[j][i] = 0; p = 0; if(num[i] > num[j] && num[i]%num[j]==0) p = num[i] / num[j]; if(num[j] > num[i] && num[j]%num[i]==0) p = num[j] / num[i]; if( ullMillerRabin(p) ) edge[i][j] = edge[j][i] = 1; } /* coloring (selecting left nodes and right nodes) */ rep(i,N) color[i] = -1; rep(i,N) if(color[i]==-1){ st_size = 0; st[st_size++] = i; color[i] = 0; while(st_size){ j = st[--st_size]; rep(k,N) if(edge[j][k] && color[k]==-1){ color[k] = (color[j]^1); st[st_size++] = k; } } } /* n1 = the number of left nodes, n2 = the number of right nodes */ node = N; S = node++; T = node++; n1 = n2 = 0; rep(i,N) if(color[i]==0) n1++; else n2++; intListMaxFlowEdgeInitAdv(node); j = k = 0; rep(i,N){ if(color[i]==0) nn[i] = j++; else nn[i] = n1 + (k++); } rep(i,N){ if(color[i] == 0) intListMaxFlowEdgeAdd(S,nn[i],cnt[i],0); else intListMaxFlowEdgeAdd(nn[i],T,cnt[i],0); } rep(i,N) if(color[i]==0) rep(j,N) if(edge[i][j]){ intListMaxFlowEdgeAdd(nn[i],nn[j],INT_INF,0); } flow = intsListMaxFlow(node,S,T); if(flow*2 == sum){ puts(Second); continue; } /* there are perfect matchings */ res = num[0]+1; rep(loop,2){ node = N; S = node++; T = node++; n1 = n2 = 0; rep(i,N) if(color[i]==0) n1++; else n2++; intListMaxFlowEdgeInitAdv(node); j = k = 0; rep(i,N){ if(color[i]==0) nn[i] = j++; else nn[i] = n1 + (k++); } rep(i,N){ if(color[i] == 0) ; /* this edge (from source to a left node) will be added one by one later */ else intListMaxFlowEdgeAdd(nn[i],T,cnt[i],0); } rep(i,N) if(color[i]==0) rep(j,N) if(edge[i][j]){ intListMaxFlowEdgeAdd(nn[i],nn[j],INT_INF,0); } rep(i,N) if(color[i]==0){ intListMaxFlowEdgeAdd(S,nn[i],cnt[i],0); flow2 = intsListMaxFlow(node,S,T); if(cnt[i] != flow2 && res > num[i]) res = num[i]; } rep(i,N) color[i] ^= 1; /* swap left nodes and right nodes, and do again */ } assert( res != num[0]+1 ); printf("%s %lld\n",First,res); } return 0; }