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