rt，大概思路是令 $dp[i][j]$ 表示第 $i$ 个问号选择 $j$ 时的最大答案，转移时枚举前一个问号点的选择，加上两点之间的固定答案，再减去因为第 $i$ 个问号的选择而变成减的值，但因为可能这个值在前面就被减去过，所以需要加回来这样。红红绿绿的真的不知道哪错了，跪求大佬捞捞 QAQ！

#include<iostream>
#define int long long
using namespace std;
const int N=3e5+5;
int t,n,tot,num[N],id[N],dp[N][30],w[N][30];
int val[27]={0,1,5,10,50,100,500,1000,5000,10000,50000,100000,500000,1000000,5000000,10000000,50000000,100000000,500000000,1000000000,5000000000,10000000000,50000000000,100000000000,500000000000,1000000000000,5000000000000};
string s;
void solve(){
	for(int i=1;i<=n;i++) num[i]=0;
	cin>>s;n=s.size();s='6'+s;
	int maxn=0;tot=0;
	for(int i=n;i>=1;i--){
		if(s[i]=='?') continue;
		if(maxn>s[i]-'A'+1) num[i]=-val[s[i]-'A'+1];
		else{
			maxn=s[i]-'A'+1;
			num[i]=val[s[i]-'A'+1];
		}
	} 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=26;j++){
			w[i][j]=w[i-1][j];
			if(s[i]-'A'+1<=j) w[i][j]+=max(0ll,num[i]);
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=26;j++) dp[i][j]=-0x3f3f3f3f3f3f3f3f;
	int ss=0;
	for(int i=1;i<=n;i++){
		ss+=num[i];
		if(s[i]!='?') continue;int pre=id[tot];id[++tot]=i;
		for(int j=1;j<=26;j++){
			for(int k=j;k<=26;k++){
				dp[tot][j]=max(dp[tot][j],dp[tot-1][k]+ss-2*w[i][j-1]+2*w[pre][j-1]);
			}
			dp[tot][j]+=val[j];
		}
		ss=0;
	}
	int ans=0;
	for(int i=1;i<=26;i++) ans=max(ans,dp[tot][i]);
	cout<<ans+ss<<endl;
	string an;int pre=n+1;
	for(int i=n;i;i--){
		if(s[i]!='?') continue;
		else{
			if(pre==n+1){
				for(int j=1;j<=26;j++) 
					if(dp[tot][j]==ans) s[i]=(char)(j+'A'-1);
			}
			else{
				int maxn=0,pl=0,j=s[id[tot+1]]-'A'+1;
				for(int k=1;k<=j;k++){
					if(dp[tot][k]-2*w[id[tot+1]][-1]+2*w[i][j-1]>maxn)
					maxn=dp[tot][k]-2*w[id[tot+1]][j-1]+2*w[i][j-1],pl=k;
				}
				s[i]=(char)(pl+'A'-1);
			}
			pre=i;tot--;
		}
	}
	for(int i=1;i<=n;i++) cout<<s[i];
	cout<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>t;while(t--) solve();
	return 0;
}