Mật khẩu

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 cùng có 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.

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

Input

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

Output

In ra \(n\) dòng, mỗi dòng là mật khẩu tương ứng tìm được.

Input

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

Output

%
morni
you?
day!

Scoring

• (50%) \(1 \le n \le 10^4\).
• (30%) \(10^4 < n \le 1.5 \cdot 10^4\).
• (20%) \(1.5 \cdot 10^4 < n \le 2 \cdot 10^4\).