Alternatives

Time Limit: 10 Seconds    Memory Limit: 32768 KB

Bob is a nice looking lucky guy and his only major problem is that he does not read very much and as so he is absolutely illiterate. He is not fond of all those commas, spelling, grammar etc. Now he is introducing a college and has to take literacy examination. He was spoken the sentence and has to write it down correctly. Of course, he has a problem doing that. As lucky guy Bob is lucky this time as well. The examination has a form of computer test and he has unlimited number of attempts to try. There are some places in the sentence Bob is unsure about. He has several variants for each of them and as so there could be quite a large number of variants of the whole sentence. Your goal is to help Bob and write the program that produces all different variants of the whole sentence based on Bob's assumptions on its parts.

Note there could be variants inside variants. Also note that as a lucky guy Bob would specify the input that will not produce more than 1000 different variants.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Input

There's single line of text (not longer than 255 characters) in the input representing the sentence. One would have variants inside denoted as

[|||].

Note that space characters are important to keep because Steve doesn't know in some cases whether words should come together or separated.

Output

Output should contain one line for each variant of the whole sentence. Sort the variants to be printed in lexicographical order.

Sample Input

1
It's [|a] b[i|ee]g problem to write correct sentences.

Sample Output

It's  beeg problem to write correct sentences.
It's  big problem to write correct sentences.
It's a beeg problem to write correct sentences.
It's a big problem to write correct sentences.

Submit