#pragma GCC optimize(2)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int dp[2000001];
int a[200001];
void solve(){
	string s;
	cin>>s;
	int n=s.length();
	for(int i=1;i<=n;i++){
		if(s[i-1]=='I'){
			a[i]=1;
		}else{
			a[i]=5;
		}
	}
	dp[n]=1;
	dp[n+1]=dp[n+2]=dp[n+3]=0;
	for(int i=n-1;i>=1;i--){
		dp[i]=dp[i+1]+1;
		if(a[i]==1){
			if(i<=n-2&&a[i+1]==1&&a[i+2]==1){
				dp[i]=min(dp[i],dp[i+3]+1);
			}
			if(a[i+1]==1){
				dp[i]=min(dp[i],dp[i+2]+1);
			}else{
				dp[i]=min(dp[i],dp[i+2]+1);
			}
		}else{
			if(a[i+1]==1){
				dp[i]=min(dp[i],dp[i+2]+1);
				if(i+2<=n&&a[i+2]==1){
					dp[i]=min(dp[i],dp[i+3]+1);
					if(i+3<=n&&a[i+3]==1){
						dp[i]=min(dp[i],dp[i+3]+1);
					}
				}
			}
		}
	}
	string ans="";
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=min(n+1,i+4);j++){
			if(dp[j]==dp[i]-1){
				if(j==i+1){
					ans+=(char)(a[i]+'0');
				}else if(j==i+2){
					if(a[i]==1){
						if(a[i+1]==1){
							ans+="2";
						}else{
							ans+='4';
						}
					}else{
						ans+="6";
					}
				}else if(j==i+3){
					if(a[i]==1){
						ans+="3";
					}else{
						ans+='7';
					}
				}else{
					ans+='8';
				}
				i=j-1;
				break;
			}
		}
	}
	for(int i=1;i<=n+1;i++){
		dp[i]=0;
	}
	cout<<ans<<endl;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;cin>>T;while(T--)
	solve();
    return 0;
}