Surbhi loves cryptography. She always devise some new technique to encode the strings for security. Here is one of her techniques...

Given a string - S of length L. Choose any range [X, Y] 0 <= X <= Y < L and reverse the characters between S[X]...S[Y]. And enclose the reversed range in square brackets. She can select as many ranges she want to reverse. But no two ranges should overlap. It can happen that she will select no range.

For example:

    S = "missyou"
    range1 = [1, 2] and range2 = [4, 6]
    Final String = "m[si]s[uoy]"

Now she has asked you to write a program that takes encoded string as input and returns the original string.

Input

The first input line contains integer T (T <= 10) which represents the number of test cases.

Each test case consists of the encoded string S.

S contains only lowercase letters and it contains no white space.

The length of the encoded string L, 1 <= L <= 10^6

Output

Print the original string for each test case in newline.

Example

Input:
2
subbuis[tnegilletni]
m[si]s[uoy]

Output:
subbuisintelligent
missyou