#include <cstdio> #include <iostream> #define LL long long #define LDB long double using namespace std; const LL mo=1e6; LL lis[16001]; struct bignum{ LL a[8001]; int len; void clear(){ for (int i=0;i<=len;i++) a[i]=0; len=0; } void one(){ clear(); a[0]=1; } void cpy(bignum &b){ clear(); len=b.len; for (int i=0;i<=len;i++) a[i]=b.a[i]; } void outp(){ printf("%lld",a[len]); for (int i=len-1;i>=0;i--) printf("%06lld",a[i]); } void sub(bignum &b){ for (int i=0;i<=len;i++){ if (i<=b.len) a[i]-=b.a[i]; if (a[i]<0){a[i]+=mo;a[i+1]--;} } while (len>0&&!a[len]) len--; } void add(bignum &b){ len=max(len,b.len); for (int i=0;i<=len;i++) a[i]+=b.a[i]; for (int i=0;i<=len;i++){ a[i+1]+=a[i]/mo; a[i]%=mo; } while (a[len+1]){ len++; a[len+1]+=a[len]/mo;a[len]%=mo; } } void mul(bignum &b){ for (int i=0;i<=len+b.len;i++) lis[i]=0; for (int i=0;i<=len;i++) for (int j=0;j<=b.len;j++) lis[i+j]+=a[i]*b.a[j]; len+=b.len; for (int i=0;i<=len;i++) a[i]=lis[i]; for (int i=0;i<=len;i++){ a[i+1]+=a[i]/mo; a[i]%=mo; } while (a[len+1]){ len++; a[len+1]+=a[len]/mo;a[len]%=mo; } while (len>0&&!a[len]) len--; } void mul(LL num){ for (int i=0;i<=len;i++) a[i]*=num; for (int i=0;i<=len;i++) a[i+1]+=a[i]/mo,a[i]%=mo; while (a[len+1]){ len++; a[len+1]+=a[len]/mo;a[len]%=mo; } while (len>0&&!a[len]) len--; } void div(LL num){ for (int i=len;i>=0;i--){ if (i) a[i-1]+=a[i]%num*mo; a[i]/=num; } while (len>0&&!a[len]) len--; } void add(LL num){ a[0]+=num; int po=0; while (a[po]>=mo){ a[po+1]+=a[po]/mo;a[po]%=mo; po++; } while (len>0&&!a[len]) len--; } void sub(LL num){ a[0]-=num; int po=0; while (a[po]<0){ LL bas=(-a[po]-1)/mo+1; a[po+1]-=bas;a[po]+=bas*mo; po++; } while (a[len+1]) len++; } int equal(bignum &b){ if (len!=b.len) return(0); for (int i=len;i>=0;i--) if (a[i]!=b.a[i]) return(0); return(1); } int bigger_or_equalto(bignum&b){ if (len>b.len) return(1); if (len<b.len) return(0); for (int i=len;i>=0;i--){ if (a[i]>b.a[i]) return(1); if (a[i]<b.a[i]) return(0); } return(1); } int equal_zero(){ return(len==0&&a[0]==0); } int bigger(bignum&b){ if (len>b.len) return(1); if (len<b.len) return(0); for (int i=len;i>=0;i--){ if (a[i]>b.a[i]) return(1); if (a[i]<b.a[i]) return(0); } return(0); } }c,tmp,bi1,bi2; int getdiv(bignum &a,bignum&b){ if (a.len<b.len) return(0); LDB numa=a.a[a.len]; if (a.len) numa*=mo,numa+=a.a[a.len-1]; int powa=max(0,a.len-1); LDB numb=b.a[b.len]; if (b.len) numb*=mo,numb+=b.a[b.len-1]; int powb=max(0,b.len-1); if (powa-powb==1) numa*=mo; return(numa/numb-1); } void divs(bignum &a,bignum &b){ tmp.clear(); int nlen=-1; for (int i=a.len;i>=0;i--){ tmp.mul(mo);tmp.add(a.a[i]); a.a[i]=0; while (getdiv(tmp,b)){ a.a[i]+=getdiv(tmp,b); if (a.a[i]!=0&&nlen==-1) nlen=i; bi1.cpy(b);bi1.mul(getdiv(tmp,b)); tmp.sub(bi1); } while (tmp.bigger_or_equalto(b)){ if (nlen==-1) nlen=i; tmp.sub(b),a.a[i]++; } } a.len=nlen; } bignum gcd(bignum x,bignum y){ if (x.equal_zero()) return(y); LL pow2=0; while (!x.equal(y)){ if ((x.a[0]%2==0)&&(y.a[0]%2==0)){ x.div(2);y.div(2); pow2++; continue; } if (x.a[0]%2==0){ x.div(2);continue; } if (y.a[0]%2==0){ y.div(2);continue; } if (y.bigger(x)) swap(x,y); x.sub(y); } for (int i=1;i<=pow2;i++) x.mul(2); return(x); } struct fact{ bignum a,b; int sig; void set(LL n){ sig=1; if (n<0) n*=-1,sig*=-1; a.clear();a.a[0]=n; b.one(); } void cpy(fact &ano){ a.cpy(ano.a);b.cpy(ano.b); sig=ano.sig; } void add(fact &ano){ bi1.cpy(a);bi1.mul(ano.b); bi2.cpy(ano.a);bi2.mul(b); if (sig==ano.sig){ bi1.add(bi2); a.cpy(bi1); }else{ if (sig==-1&&ano.sig==1) swap(bi1,bi2); if (bi1.bigger(bi2)){ bi1.sub(bi2); a.cpy(bi1); sig=1; }else{ bi2.sub(bi1); a.cpy(bi2); sig=-1; } } b.mul(ano.b); } void sub(LL num){ tmp.cpy(b);tmp.mul(num); if (sig==-1){ a.add(tmp); }else{ if (a.bigger(tmp)) a.sub(tmp); else{ tmp.sub(a); a.cpy(tmp); sig=-1; } } } void add(LL num){ tmp.cpy(b);tmp.mul(num); if (sig==1){ a.add(tmp); }else{ if (a.bigger(tmp)) a.sub(tmp); else{ tmp.sub(a); a.cpy(tmp); sig=1; } } } void mul(LL num){ if (num<0) sig*=-1,num*=-1; a.mul(num); } void div(LL num){ if (num<0) sig*=-1,num*=-1; b.mul(num); } void outp(int cas){ printf("Case #%d: ",cas); if (sig==-1) printf("-"); c.clear(); c=gcd(a,b); divs(a,c); divs(b,c); a.outp();printf(" ");b.outp(); } }ans1,ans2,ans3,bas; int bigger(fact &a,fact &b){ if (a.sig==1&&b.sig==-1) return(1); if (a.sig==-1&&b.sig==1) return(0); bi1.cpy(a.a);bi1.mul(b.b); bi2.cpy(b.a);bi2.mul(a.b); if (bi1.bigger(bi2)){ if (a.sig==1) return(1);else return(0); }else{ if (a.sig==-1) return(1);else return(0); } } int T,multab[2333][2],divtab[2333][2]; LL n,m,num[2333]; char opt[2333][11]; int main(){ scanf("%d",&T); for (int cas=1;cas<=T;cas++){ scanf("%lld%lld",&n,&m); LL posi=0,nega=0; for (int i=0;i<=1000;i++) multab[i][0]=multab[i][1]=divtab[i][0]=divtab[i][1]=0; int allposi=1,mul0=0,mulsig=1; for (int i=1;i<=m;i++){ scanf("%s%lld",&opt[i],&num[i]); if (opt[i][0]=='+'){ if (num[i]>0) posi+=num[i];else nega-=num[i]; }else if (opt[i][0]=='-'){ if (num[i]>0) nega+=num[i];else posi-=num[i]; }else if (opt[i][0]=='*'){ if (num[i]>0) multab[num[i]][0]++;else multab[-num[i]][1]++; if (num[i]==0) mul0=1; if (num[i]<0) allposi=0,mulsig*=-1; }else{ if (num[i]>0) divtab[num[i]][0]++;else divtab[-num[i]][1]++; if (num[i]<0) allposi=0; } } if (allposi){ if (mul0){ ans1.set(posi); for (int i=1;i<=1000;i++) for(int j=1;j<=multab[i][0];j++) ans1.mul(i); ans1.outp(cas); }else{ ans1.set(n); ans1.sub(nega); for (int i=1;i<=1000;i++) for (int j=1;j<=divtab[i][0];j++) ans1.div(i); ans1.add(posi); for (int i=1;i<=1000;i++) for(int j=1;j<=multab[i][0];j++) ans1.mul(i); ans2.set(n); ans2.add(posi); for (int i=1;i<=1000;i++) for(int j=1;j<=multab[i][0];j++) ans2.mul(i); ans2.sub(nega); for (int i=1;i<=1000;i++) for (int j=1;j<=divtab[i][0];j++) ans2.div(i); if (bigger(ans2,ans1)) ans1.cpy(ans2); ans2.set(n); for (int i=1;i<=1000;i++) for (int j=1;j<=divtab[i][0];j++) ans2.div(i); ans2.add(posi); for (int i=1;i<=1000;i++) for(int j=1;j<=multab[i][0];j++) ans2.mul(i); ans2.sub(nega); if (bigger(ans2,ans1)) ans1.cpy(ans2); ans2.set(n); for (int i=1;i<=1000;i++) for(int j=1;j<=multab[i][0];j++) ans2.mul(i); ans2.sub(nega); for (int i=1;i<=1000;i++) for (int j=1;j<=divtab[i][0];j++) ans2.div(i); ans2.add(posi); if (bigger(ans2,ans1)) ans1.cpy(ans2); ans1.outp(cas); } }else{ bas.set(1); for (int i=1;i<=1000;i++){ for (int j=1;j<=multab[i][0];j++) bas.mul(i); for (int j=1;j<=multab[i][1];j++) bas.mul(-i); } for (int i=1;i<=1000;i++){ for (int j=1;j<=divtab[i][0];j++) bas.div(i); for (int j=1;j<=divtab[i][1];j++) bas.div(-i); } if (mul0) ans1.set(0);else ans1.cpy(bas),ans1.mul(n); bas.set(1); for (int i=1;i<=1000;i++){ for (int j=1;j<=multab[i][0];j++) bas.mul(i); for (int j=1;j<=multab[i][1];j++) bas.mul(i); } int mini=1e9; for (int i=1;i<=1000;i++) if (multab[i][1]) mini=min(mini,i); for (int i=1;i<=1000;i++) if (divtab[i][1]) mini=min(mini,i); if (mulsig==1){ ans2.cpy(bas);ans2.mul(posi); ans3.cpy(bas);ans3.mul(nega);ans3.div(mini); ans1.add(ans2);ans1.add(ans3); ans1.outp(cas); }else{ ans2.cpy(bas);ans2.mul(nega); ans3.cpy(bas);ans3.mul(posi);ans3.div(mini); ans1.add(ans2);ans1.add(ans3); ans1.outp(cas); } } printf("\n"); } }