Để mã hóa một khóa ~s~ không rỗng, đầu tiên điệp viên chọn một chuỗi ~t~ sao cho chuỗi ~s~ là một chuỗi tiền tố của ~t~, và chuỗi nghịch đảo của ~s~ là hậu tố của chuỗi ~t~. Trong trường hợp này, chuỗi ~t~ có thể ghi các ký hiệu không liên quan đến chuỗi ~s~. Sau đó, một số ngẫu nhiên ~m~ (có thể ~m = 0)~ ký tự ngẫu nhiên được đưa vào bên trái của ~t~, mà ~m~ ký tự ngẫu nhiên được thêm vào bên phải ~t~. Bây giờ, chuỗi ~t~ là mã hóa của ~s~.

Rõ ràng với ~t~, có thể có nhiều ~s~. Do đó, người ta quyết định rằng khóa ~s~ phải là chuỗi dài nhất trong tất cả các tùy chọn có thể, và trong trường hợp có nhiều tùy chọn dài nhất, chọn số lượng các ký tự ngẫu nhiên thêm vào bên trái và vào bên phải là tối thiểu, nghĩa là, chuỗi ~t~ có chiều dài tối đa. Bạn cần phải thực hiện thuật toán phục hồi khoá ~s~ từ phiên bản được mã hóa ~t~.

Input

Dòng đầu tiên ghi số nguyên ~n~ - số khóa mà bạn cần phải giải mã.

Mỗi dòng trong ~n~ dòng sau là một chuỗi mã hóa ~t~, chỉ gồm chữ cái thường trong bảng chữ cái Latinh. Tổng chiều dài của tất cả các khóa không vượt quá 100.000 ký tự. Đảm bảo rằng mỗi phiên bản mật mã có ít nhất một khoá không rỗng.

Output

Với mỗi bản mã ~t~, in ra trên một dòng khóa ~s~ tương ứng.

Sample Input

3
ababc
ababa
cxbaydzabxe

Sample Output

bab
ababa
xba