Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Little Vitaly yêu ‎‎các thuật toán khác nhau‎‎. Hôm nay ông ấy đã phát minh ra một thuật toán mới chỉ dành cho bạn. Thuật toán của Vitaly làm việc với chuỗi ‎‎ ‎‎s‎‎, bao gồm các ký tự "‎‎x‎‎" và "‎‎y‎‎", và sử dụng hai hoạt động sau đây trong thời gian chạy:‎

1. Tìm thấy hai ký tự liên tiếp trong chuỗi  mà kĩ tự đầu tiên của cặp bằng "‎‎y‎‎", và thứ hai bằng "‎‎x‎‎" và trao đổi chúng. Nếu có nhiều cặp phù hợp, chọn các cặp các ký tự nằm gần đầu của chuỗi s hơn.
2. ‎Tìm trong ký tự liên tiếp hai chuỗi mà kí tự  đầu tiên của cặp bằng "‎‎x‎‎" và thứ hai bằng "‎‎y‎‎". Loại bỏ các ký tự từ chuỗi. Nếu có nhiều cặp phù hợp, chọn các cặp các ký tự nằm gần đầu chuỗi s hơn.

‎Đầu vào cho các thuật toán mới là chuỗi ‎‎ ‎‎s‎‎, và thuật toán như sau:‎

1. ‎ Nếu bạn có thể áp dụng ít nhất một trong các hoạt động cho các chuỗi thì đi tới bước 2 của thuật toán. Nếu không, dừng thực hiện các thuật toán và in chuỗi hiện hành. ‎
2. ‎ Nếu bạn có thể áp dụng các thao tác 1 thì  áp dụng nó. Nếu không, áp dụng hoạt động 2. Sau khi bạn áp dụng các hoạt động, đi tới bước 1 của thuật toán. ‎

‎Bây giờ Vitaly thắc mắc, những gì sẽ được in ra nếu nhận được đầu vào chuỗi ‎‎ ‎‎s‎‎.‎

Input

Dòng đầu tiên là số test t.

Trong mỗi test có chứa một chuỗi trống ‎‎ ‎‎s‎‎. ‎

‎Chúng tôi đảm bảo rằng các chuỗi chỉ bao gồm ký tự "‎‎x‎‎" và "‎‎y‎‎". Nó được đảm bảo rằng các chuỗi bao gồm nhiều nhất ‎‎10‎^‎5‎‎ kí tự và kết quả thực hiện các thuật toán sẽ không là một chuỗi rỗng.‎

Output

Gồm n dòng, mỗi dòng là chuỗi s sau khi thực hiện thuật toán.

Example

Input:
3
x
yxyxy
xxxxxy

Output:
x
y
xxxx 

Giải thích:
‎Trong test 1, thuật toán sẽ kết thúc sau bước đầu tiên của thuật toán, nó không thể áp dụng bất kỳ hoạt động nào. Vì vậy, các chuỗi sẽ không thay đổi.‎
‎Trong test 2 chuyển đổi sẽ như thế này:‎
‎ Chuỗi "‎‎yxyxy‎‎" biến thành chuỗi "‎‎xyyxy‎‎"; ‎
‎ Chuỗi "‎‎xyyxy‎‎" biến thành chuỗi "‎‎xyxyy‎‎"; ‎
‎ Chuỗi "‎‎xyxyy‎‎" biến thành chuỗi "‎‎xxyyy‎‎"; ‎
‎ Chuỗi "‎‎xxyyy‎‎" biến thành chuỗi "‎‎xyy‎‎"; ‎
‎ Chuỗi "‎‎xyy‎‎" biến thành chuỗi "‎‎y‎‎". ‎
‎Kết quả là sau biến đổi s ta được chuỗi "‎‎y‎‎". ‎
‎Trong test 3 chỉ có một chuyển đổi sẽ diễn ra: chuỗi "‎‎xxxxxy‎‎" biến thành chuỗi "‎‎xxxx‎‎". Vì vậy, câu trả lời sẽ là chuỗi "‎‎xxxx‎‎".‎