시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 362 156 135 49.451%

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

예제 입력 1

2
3
7

예제 출력 1

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

힌트

W3sicHJvYmxlbV9pZCI6Ijc0OTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIwIFx1YjljY1x1YjRlNFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+MVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjNGY0IFx1YzIxOFx1YzVmNCAxIDIgMyAuLi4gTlx1Yzc0NCBcdWMwZGRcdWFjMDFcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YWNlMCAmIzM5OysmIzM5O1x1YjA5OCAmIzM5Oy0mIzM5OywgXHViNjEwXHViMjk0ICYjMzk7ICYjMzk7KFx1YWNmNVx1YmMzMSlcdWM3NDQgXHVjMjJiXHVjNzkwIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWMwYmRcdWM3ODVcdWQ1NThcdWM3OTAoK1x1YjI5NCBcdWIzNTRcdWQ1NThcdWFlMzAsIC1cdWIyOTQgXHViZTdjXHVhZTMwLCBcdWFjZjVcdWJjMzFcdWM3NDAgXHVjMjJiXHVjNzkwXHViOTdjIFx1Yzc3NFx1YzViNCBcdWJkOTlcdWM3NzRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNCkuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWI5Y2NcdWI0ZTAgXHVjMjE4XHVjMmRkXHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWFjZTAgXHVhZGY4IFx1YWNiMFx1YWNmY1x1YWMwMCAwXHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1YzBiNFx1ZDUzY1x1Yzc5MC48XC9wPlxyXG5cclxuPHA+Tlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjIFx1YzIxOFx1YzJkZFx1Yzc1OCBcdWFjYjBcdWFjZmNcdWFjMDAgMFx1Yzc3NCBcdWI0MThcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIxOFx1YzJkZFx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0KCZsdDsxMCkuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQ0IFx1Yzc5MFx1YzVmMFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCgzICZsdDs9IE4gJmx0Oz0gOSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IEFTQ0lJIFx1YzIxY1x1YzExY1x1YzVkMCBcdWI1MzBcdWI3N2MgXHVhY2IwXHVhY2ZjXHVhYzAwIDBcdWM3NzQgXHViNDE4XHViMjk0IFx1YmFhOFx1YjRlMCZuYnNwO1x1YzIxOFx1YzJkZFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWNiMFx1YWNmY1x1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNzQ0IFx1Yjc0NFx1YzZjYyBcdWFkNmNcdWJkODRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzQ5MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ilplcm8iLCJkZXNjcmlwdGlvbiI6IjxwPkxldCZsc3F1bztzIGNvbnNpZGVyIHRoZSBzZXF1ZW5jZSBvZiBkaWdpdHMgZnJvbSAxIHRocm91Z2ggTiAod2hlcmUgTj05KSBpbiBpbmNyZWFzaW5nIG9yZGVyOiAxIDIgMyAuLi4gTi4gTm93IGluc2VydCBlaXRoZXIgYSAmIzM5OysmIzM5OyBmb3IgYWRkaXRpb24gb3IgYSAmIzM5Oy0mIzM5OyBmb3Igc3VidHJhY3Rpb24gb3IgYSAmIzM5OyAmIzM5OyBbYmxhbmtdIHRvIHJ1biB0aGUgZGlnaXRzIHRvZ2V0aGVyLCBiZXR3ZWVuIGVhY2ggcGFpciBvZiBkaWdpdHMgKG5vdCBpbiBmcm9udCBvZiB0aGUgZmlyc3QgZGlnaXQpLiBDYWxjdWxhdGUgdGhlIHJlc3VsdCB0aGF0IG9mIHRoZSBleHByZXNzaW9uIGFuZCBzZWUgaWYgeW91IGdldCB6ZXJvLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGZpbmQgYWxsIHNlcXVlbmNlcyBvZiBsZW5ndGggTiB0aGF0IHByb2R1Y2UgYSB6ZXJvIHN1bS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgKCZsdDsxMCkuIFNpbmdsZSB0ZXN0IGNhc2UgaXMgcmVwcmVzZW50ZWQgYnkgc2luZ2xlIGxpbmUgdGhhdCBjb250YWlucyB0aGUgaW50ZWdlciBOICgzICZsdDs9IE4gJmx0Oz0gOSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIGluIEFTQ0lJIG9yZGVyLCBwcmludCBlYWNoIHNlcXVlbmNlIHRoYXQgY2FuIGNyZWF0ZSAwIHN1bSB3aXRoIGEgJiMzOTsrJiMzOTssICYjMzk7LSYjMzk7LCBvciAmIzM5OyAmIzM5OyAoc3BhY2UpIGJldHdlZW4gZWFjaCBwYWlyIG9mIG51bWJlcnMuIFNwYWNlIHNob3dzIHRoYXQgdGhlIGRpZ2l0cyBydW4gdG9nZXRoZXIuIERpZmZlcmVudCB0ZXN0IGNhc2VzIHNob3VsZCBiZSBzZXBhcmF0ZWQgYnkgYW4gZW1wdHkgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=