You are given a string S consisting of lowercase English letters and the character <.
The character < represents a backspace operation.
When processing the string from left to right:
If the current character is a lowercase letter, it is added to the result.
If the current character is <, it removes the most recently added character (if any).
If there is no character to remove, the operation does nothing.
Your task is to process the string and print the final result after applying all backspace operations.
The first line contains a single integer T, the number of test cases.
The next T lines each contain a single string S.
For each test case, print the resulting string.
1 ≤ T ≤ 10^5
1 ≤ |S| ≤ 10^6
| Example Input | Example Output |
|---|---|
3 ab |
ac ad asd |