Trò Chơi Alice-Bob

Cho xâu $s=s_1{s}_2\dots s_n$ độ dài $n$ gồm các chữ cái thường. Alice và Bob chơi trò chơi sau, lần lượt Alice đi trước:

• Mỗi lượt, người chơi chọn một vị trí $i$ chưa được chọn trước đó, và đổi $s_i$ thành một chữ cái thường khác (khác với giá trị hiện tại).
• Trò chơi kết thúc khi mọi vị trí đều đã được chọn.

Alice muốn xâu cuối cùng càng nhỏ về thứ tự từ điển càng tốt; Bob muốn xâu cuối càng lớn càng tốt. Cả hai chơi tối ưu. In ra xâu cuối cùng.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ ($1\le t\le 1000$) — số test.
• Mỗi test: một dòng chứa xâu $s$ ($1\le |s|\le 50$, gồm các chữ cái thường).

Dữ liệu ra

Với mỗi test, in ra xâu cuối cùng trên một dòng.

Ràng buộc

• $1\le t\le 1000$
• $1\le |s|\le 50$
• $s$ chỉ gồm các chữ cái thường tiếng Anh.

Ví dụ

Ghi chú

Chỉ vị trí — không phải giá trị — quyết định ai sẽ đi: vị trí lẻ (1, 3, 5, …) là Alice, vị trí chẵn là Bob.