Time Limit: 1000 MS Memory Limit: 65536 K

## Description

Some dictionaries use a word pattern that consists of letters,
'?' symbols which each denote exactly one letter,
and '*' symbols which each denote zero or more letters.
Interestingly, some patterns represent the same set of words.
For example, "*??*a" and "?*?a" (quotes for clarity only)
patterns both represent all words that consist of three or
more letters and end with 'a'.
You will be given a pattern. You should tell me the shortest pattern
that represents the same set of words as the given pattern.
Output the lexicographically first in case of tie.
## Input

The first line of the input will be a integer to represent the number of test cases.
For each case there is only one line contains only a string
which contains only letters ('a'-'z', 'A'-'Z'), '?' and '*'.
( 1 <= The length of the string <= 1000 )
Note that '*' comes before '?' in the lexicographical order.
There is a blank line before each test case.
## Output

For each test case output the answer on a line.
## Sample Input

3
*??*a
*b**a*
T***nd?*
## Sample Output

*??a
*b*a*
T*nd*?

## Source