Vô diện đang có một đoạn văn bản muốn gửi cho Almira nhưng lo sợ những người không liên quan đọc hiểu. Một ngày đẹp trời, Vô diện tìm ra được một các mã hóa đoạn văn bản này để có thể giấu được thông điệp. Các bạn hãy giúp Vô diện mã hóa thông điệp theo quy tắc sau:

• Một chuỗi con của các chữ cái giống hệt nhau được thay thế bằng duy nhất 1 chữ cái đó và tiếp theo sau đó là số thập lúc phân (Hex) của số lần xuất hiện của chữ cái đó.
• Tiếp theo chúng ta đảo ngược chuỗi vừa thu được và in ra bản mã hóa thông điệp

Lưu ý: Các ký tự thập lục phân đều được viết dưới dạng chữ thường

Input:

• Dòng đầu tiên là số nguyên n là số testcase \(( 0 < n < 100)\)
• n dòng tiếp theo là bản thông điệp Vô diện muốn gửi ứng với mỗi test case. (Độ dài thông điệp không quá 50 ký tự)

Output:

• n dòng tiếp theo là bản mã hóa của thông điệp ứng với mỗi testcase

Ví dụ:

Input 1:

1
aaaaaaaaaaa

Ouput 1:

ba

Giải thích:

• Bước 1: a11
• Bước 2: 11 là b trong bảng mã thập lục => a11 <=> ab
• Bước 3: ba

Input 2:

2
ababab
abc

Output 2:

1b1a1b1a1b1a
1c1b1a