High School Programming League Problems Archive

Given a sequence of digits, insert the character = (equality sign) and two operators: + (plus) and - (minus) so as to form an equality of two arithmetic expressions.

Rules:

• Do not rearrange the given sequence of digits.
• Place in between every two consecutive digits in the sequence exactly one of the symbols: plus, minus, or equality sign.
• Use the equality sign exactly once.

If there is more than one solution, find all of them.

Input

First, you are given T, the number of test cases (T ≤ 10000). The test cases follow, one test per line. Each of the test cases consists of a sequence of digits. There are at least 2 and no more than 10 digits in the sequence. Digits are separated by spaces.

Output

For each of the test cases print all requested equalities, one per line, in arbitrary order.

Example

Input:
3
2 3
1 0 1 0
3 2 1

Output:
1=0+1-0
1=0+1+0
1-0=1-0
1-0=1+0
1+0=1-0
1+0=1+0
1-0-1=0
1+0-1=0
3=2+1
3-2=1

Scoring

There are five sets of tests, each set worth 2 points

Set 1 - two digits in every test case.
Set 2 - three digits in every test case.
Set 3 - up to five digits in every test case.
Set 4 - up to ten digits in every test case, output size does not exceed 300KB
Set 5 - up to ten digits in every test case, output size does not exceed 2.5MB