Making Zero

Time limit1sMemory limit128 MB

Summary

Insert +, -, or a space between consecutive numbers 1 to N and print every expression that evaluates to 0, in ASCII order.

Level: Medium4 of 10
Topics: Backtracking, Brute force, Implementation
Solved: No attempts yet

Problem

Consider the sequence 1 2 3 ... N, the integers from $1$ to $N$ written in ascending order.

Between every pair of adjacent numbers, insert exactly one of the following:

+ : addition
- : subtraction
(a space) : concatenate the two numbers into a single number

Evaluate the resulting expression. We want to find every case whose value equals $0$ .

Given an integer $N$ , write a program that prints every expression whose value is $0$ .

Input

The first line contains the number of test cases $T$ ( $T < 10$ ).

Each of the following lines contains one natural number $N$ ( $3 \le N \le 9$ ).

Output

For each test case, print every expression whose value is $0$ , one per line, in ASCII (lexicographic) order. The ASCII order of the operator characters is space ( ), then +, then -.

Separate the outputs of different test cases with a single blank line. Do not print a blank line after the last test case.

Examples1

Example 1

Input

2
3
7

Expected output

1+2-3

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7