Trong một buổi thi lập trình, thầy giáo yêu cầu học sinh gửi tệp bài thi được đặt mật khẩu cùng với một xâu ký tự đã dấu mật khẩu để mở tệp bài thi vào email của thầy giáo. Mật khẩu được dấu trong một xâu ký tự là một xâu con gồm các ký tự khác nhau, không chứa dấu cách trắng và có độ dài lớn nhất. Nếu có nhiều xâu con gồm các ký tự khác nhau, không chứa dấu cách trắng và có độ dài lớn nhất bằng nhau thì xâu con cuối cùng trong xâu ký tự là xâu mật khẩu để mở tệp.

Yêu cầu: Xác định mật khẩu được giấu trong một xâu ký tự.

INPUT

• Dòng ~1~ chứa một số nguyên dương ~n~ ~(1 ≤ n ≤ 2 \times 10^{4})~ là số lượng các dòng văn bản có trong tệp.
• ~n~ dòng tiếp theo, mỗi dòng chứa một xâu không vượt quá ~256~ ký tự bao gồm các chữ cái, chữ số, ký tự đặc biệt, dấu cách trống.

OUTPUT

Gồm các dòng tương ứng là mật khẩu được giấu trong xâu ký tự.

SUBTASKS

• ~50 \%~ số test ứng với ~1 ≤ n ≤ 10^{4}~.
• ~30 \%~ số test ứng với ~10^{4} < n ≤ 1.5 \times 10^{4}~.
• ~20 \%~ số test ứng với ~1.5 \times 10^{4} < n ≤ 2 \times 10^{4}~.

SAMPLE INPUT

3
Good morning!
How are you?
Have a nice day!

SAMPLE OUTPUT

morni
you?
day!