Mật khẩu của Vasya

Một mật khẩu hợp lệ là xâu chỉ gồm chữ cái Latin thường, chữ cái Latin hoa và chữ số, đồng thời phải chứa ít nhất một chữ số, ít nhất một chữ hoa và ít nhất một chữ thường.

Cho xâu $s$ gồm các chữ cái Latin thường, chữ hoa và chữ số. Bạn phải thực hiện đúng một lần thao tác: chọn một xâu con liên tiếp của $s$ và thay nó bằng một xâu khác có cùng độ dài, cũng chỉ gồm chữ thường, chữ hoa và chữ số. Sau thao tác, $s$ phải trở thành mật khẩu hợp lệ.

Độ dài của xâu con bị thay được tính như sau: xét tất cả các vị trí bị đổi ký tự. Nếu không có vị trí nào thì độ dài bằng $0$; ngược lại độ dài bằng vị trí cuối cùng trừ vị trí đầu tiên rồi cộng $1$. Ví dụ, biến đổi abcdef thành a7cdEf có các vị trí thay đổi là $2$ và $5$, nên độ dài bằng $(5-2)+1=4$.

Hãy đưa ra một mật khẩu hợp lệ sao cho độ dài xâu con bị thay là nhỏ nhất có thể. Dữ liệu đảm bảo luôn tồn tại đáp án.

Dữ liệu vào

• Dòng đầu chứa số nguyên $T$: số lượng bộ dữ liệu.
• $T$ dòng tiếp theo, mỗi dòng chứa một xâu $s$ gồm chữ cái Latin thường, chữ hoa và chữ số.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa mật khẩu thu được. Nếu có nhiều đáp án cùng đạt độ dài nhỏ nhất, in ra bất kỳ đáp án nào.

Ràng buộc

• $1\le T\le 100$
• $3\le |s|\le 100$

Ví dụ