Cho bảng giá trị các chữ cái Latin hoa từ A đến Z: A = 1, B = 5, C = 10, D = 50, E = 100, F = 500, …, Y = 10¹², Z = 5 × 10¹². Cụ thể, chữ cái có chỉ số 2j (A có chỉ số 0) mang giá trị 10ʲ; chữ cái có chỉ số 2j + 1 mang giá trị 5 × 10ʲ.

Giá trị của một xâu được tính như sau: mỗi ký tự đóng góp giá trị dương nếu bên phải nó không có ký tự mang giá trị lớn hơn; ngược lại, ký tự đó đóng góp giá trị âm. Cộng các đóng góp để được giá trị của xâu.

Cho t xâu gồm các chữ cái Latin hoa và dấu ?. Thay mỗi dấu ? bằng một chữ cái Latin hoa để giá trị của xâu lớn nhất. In giá trị lớn nhất và một xâu đạt giá trị đó.

Dữ liệu vào

Dòng đầu chứa t (1 ≤ t ≤ 50000).

Mỗi dòng trong t dòng tiếp theo chứa một xâu không rỗng. Tổng độ dài các xâu không vượt quá 300000.

Kết quả

Với mỗi xâu, in hai dòng: dòng đầu chứa giá trị lớn nhất ở hệ thập phân, dòng tiếp theo chứa xâu sau khi thay thế. Nếu có nhiều đáp án tối ưu, in một đáp án bất kỳ.

Ví dụ

Input

4
BBBC
????
A?B?C?D
YYYYY?

Output

-5
BBBC
20000000000000
ZZZZ
15000000000034
AZBZCZD
6000000000000
YYYYYY

Đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Mỗi test được chấm độc lập.