모스크바 숫자

당신은 아마 로마 숫자를 알고 있을 것이다. 또 모스크바가 제3의 로마라는 말도 들어 보았을 것이다. 그래서 로마 숫자를 본떠 그보다 발전된 체계인 모스크바 숫자를 만들었다.

모스크바 숫자의 숫자는 영문 대문자 A부터 Z까지이다. 모스크바 숫자는 숫자가 여러 개 이어진 문자열이다. 각 숫자의 값은 아래 표와 같다.

수의 값은 각 숫자가 기여하는 값의 합이다. 어떤 숫자의 오른쪽에 그 숫자보다 큰 숫자가 없으면 그 숫자의 기여값은 숫자의 값과 같다. 그렇지 않으면 기여값은 숫자의 값에 음수 부호를 붙인 값이다.

예를 들어 BBA의 값은 5+5+1=11이다. BBBC의 값은 -5+(-5)+(-5)+10=-5이다. ABC의 값은 -1+(-5)+10=4이다. BAC의 값은 -5+(-1)+10=4이다. ACA의 값은 -1+10+1=10이다.

영문 대문자와 물음표 ?로 이루어진 문자열이 여러 개 주어진다. 각 물음표를 모스크바 숫자의 숫자 중 하나로 바꿀 때, 만들 수 있는 가장 큰 수를 구하라.

첫 줄에 정수 $t$ ($1 \le t \le 50000$)가 주어진다. 이는 문자열의 개수이다. 다음 $t$개의 줄에 영문 대문자와 ?로 이루어진 문자열 $s_i$가 한 줄에 하나씩 주어진다. 모든 문자열 길이의 합은 300000을 넘지 않는다.

각 문자열마다 두 줄을 출력한다. 첫 줄에는 만들 수 있는 가장 큰 수의 값을 십진수로 출력한다. 둘째 줄에는 그 값을 얻도록 물음표를 영문 대문자로 바꾼 문자열을 출력한다.