#include <bits/stdc++.h> using namespace std; #define int long long #define i128 __int128 #define endl "\n" i128 CC[1021][1021]; int n,q; bool p[4][150]; int s[4]; inline i128 gcd(i128 a,i128 b){ return b==0?a:gcd(b,a%b); } i128 f[130][61][61]; i128 g[130][61][61]; inline void prt(i128 x){ stack<char>p; while(x)p.push(x%10+'0'),x/=10; while(!p.empty())cout<<p.top(),p.pop(); } inline i128 calc(int q,int c1,int c2,int c3){ int A=s[1],B=s[2],C=s[3]; i128 res=0; for(int a=0;a<=c1;a++){ if((2*a-c1+c2-A+B)%2==1)continue; int b=(2*a-c1+c2-A+B)/2; if(((2*b-c2+c3-B+C))%2==1)continue; int c=(2*b-c2+c3-B+C)/2; int t=A-a-c2+b-c3+c; if(b>=0&&c>=0&&t>=0) res+=CC[c1][a]*CC[c2][b]*CC[c3][c]*CC[q-c1-c2-c3][t]; } return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("exam.in","r",stdin); // freopen("SS.out","w",stdout); int t; cin>>t; for(int i=0;i<=120;i++){ CC[i][0]=1; for(int j=1;j<=i;j++) CC[i][j]=CC[i-1][j-1]+CC[i-1][j]; } // prt(CC[120][60]); // cout<<endl; while(t--){ cin>>n>>q; // cout<<n<<" "<<q<<endl; // cout.flush(); for(int i=1;i<=n;i++){ for(int j=1;j<=q;j++){ char x; cin>>x; if(x=='T')p[i][j]=1; else p[i][j]=0; // cout<<p[i][j]; } cin>>s[i]; if(s[i]*2>q){ for(int j=1;j<=q;j++) p[i][j]^=1; s[i]=q-s[i]; } } if(n==1){ for(int i=1;i<=q;i++) if(p[1][i])cout<<"F"; else cout<<"T"; cout<<" "<<q-s[1]<<"/"<<1<<endl; n=q=-1; continue; } else if(n==2){ for(int i=0;i<=q+1;i++) for(int j=0;j<=q/2;j++) for(int k=0;k<=q/2;k++) g[i][j][k]=f[i][j][k]=0; f[0][0][0]=1; for(int i=1;i<=q;i++) for(int j=0;j<i&&j<=q/2;j++) for(int k=0;k<i&&k<=q/2;k++) for(int w=0;w<=1;w++) f[i][j+(w==p[1][i])][k+(w==p[2][i])]+=f[i-1][j][k]; // cout<<(int)f[q][s[1]][s[2]]<<endl; g[q+1][0][0]=1; for(int i=q;i>=1;i--) for(int j=0;j<q-i+1&&j<=q/2;j++) for(int k=0;k<q-i+1&&k<=q/2;k++) for(int w=0;w<=1;w++) g[i][j+(w==p[1][i])][k+(w==p[2][i])]+=g[i+1][j][k]; // cout<<(int)g[1][s[1]][s[2]]<<endl; i128 res=0; i128 tot=f[q][s[1]][s[2]]; for(int i=1;i<=q;i++){ i128 mx[2]; for(int w=0;w<=1;w++){ int a=s[1]-(w==p[1][i]),b=s[2]-(w==p[2][i]); i128 ct=0; for(int j=0;j<=a;j++) for(int k=0;k<=b;k++) ct+=f[i-1][j][k]*g[i+1][a-j][b-k]; mx[w]=ct; } if(mx[1]>mx[0])cout<<"T"; else cout<<"F"; res+=max(mx[1],mx[0]); } // cout<<(int)res<<" "<<(int)tot<<endl; // cout.flush(); i128 t=gcd(res,tot); res/=t,tot/=t; cout<<" "; prt(res),cout<<"/"; prt(tot),cout<<endl; } else{ i128 res=0,tot=0; int c1=0,c2=0,c3=0; for(int i=1;i<=q;i++){ if(p[1][i]!=p[2][i]&&p[1][i]!=p[3][i])c1++; if(p[2][i]!=p[1][i]&&p[2][i]!=p[3][i])c2++; if(p[3][i]!=p[2][i]&&p[3][i]!=p[1][i])c3++; } tot=calc(q,c1,c2,c3); for(int i=1;i<=q;i++){ if(p[1][i]!=p[2][i]&&p[1][i]!=p[3][i])c1--; if(p[2][i]!=p[1][i]&&p[2][i]!=p[3][i])c2--; if(p[3][i]!=p[2][i]&&p[3][i]!=p[1][i])c3--; i128 ct[2]; for(int w=0;w<=1;w++){ for(int j=1;j<=n;j++) s[j]-=p[j][i]==w; ct[w]=calc(q-1,c1,c2,c3); for(int j=1;j<=n;j++) s[j]+=p[j][i]==w; } if(p[1][i]!=p[2][i]&&p[1][i]!=p[3][i])c1++; if(p[2][i]!=p[1][i]&&p[2][i]!=p[3][i])c2++; if(p[3][i]!=p[2][i]&&p[3][i]!=p[1][i])c3++; if(ct[1]>ct[0])cout<<"T"; else cout<<"F"; res+=max(ct[1],ct[0]); } i128 t=gcd(res,tot); res/=t,tot/=t; cout<<" "; prt(res),cout<<"/"; prt(tot),cout<<endl; } } cout.flush(); return 0; }