시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB1711068059.259%

문제

만칼라는 보드 게임의 한 종류로, 여러 변형 판이 존재한다.

그 중 가장 간단한 종류인 1인용 만칼라 게임 Tchoukaillon에 대해 살펴볼 것이다.

Tchoukaillon는 여러 개의 빈칸과 하나의 Roumba로 이루어진 보드 위에서 진행된다.

가장 왼쪽의 빈칸은 Roumba이며, 처음엔 항상 비어있는 상태여야 한다.

게임은 다음과 같이 진행된다. 우선, 각 칸을 B[N]이라 할 때, B[N]에 N개의 구슬이 들어 있는 칸을 찾는다. 그런 칸이 여러 개라면 아무 것이나 선택해도 상관없다. 만일 B[N]=N인 칸이 없다면 그 판은 패배이다.

위의 예제에서는 맨 첫 줄을 보면 된다. 3번 칸을 선택한 상황이다.

이제 고른 칸의 구슬을 Roumba와 B[1], B[2], ... , B[N-1]에 하나씩 고르게 나누어준다.

위의 시행을 계속 반복하여 모든 구슬이 Roumba로 들어간다면 게임을 성공적으로 마치게 되는 것이고, 이처럼 성공이 가능한 모든 게임판을 승리하는 게임판이라고 한다. 모든 정수 N에 대해, 구슬이 총 N개일 때의 승리하는 게임판은 항상 유일하다. 따라서 위에서의 Roumba를 뺀 보드판의 초기 상태 { 0, 1, 3 } 은 구슬이 4개일 때의 유일한 승리하는 게임판이다.

총 구슬의 개수 N이 주어지면 승리하는 게임판을 출력하라.

입력

첫 줄에 테스트 케이스의 수 P가 주어진다. (1 ≤ P ≤ 1000)

각 테스트 케이스는 테스트 케이스의 번호 T와 보드판에 들어갈 구슬의 총 개수 N으로 이루어져 있다.

출력

각 테스트 케이스마다 첫 줄에 테스트 케이스의 번호 T와 구슬이 하나 이상 담겨 있는 보드판의 마지막 위치 B를 출력한다.

그 후 승리하는 게임판의 상태를 B개의 정수로 출력하는데, 수는 10개 단위로 끊어서 출력해야 한다.

모든 테스트 케이스에서 B는 80을 넘지 않는다.

예제 입력 1

3
1 4
2 57
3 500

예제 출력 1

1 3
0 1 3
2 12
1 2 2 2 2 6 2 4 6 8
10 12
3 39
0 2 2 1 3 2 2 2 6 7
5 0 6 12 2 6 10 14 18 1
3 5 7 9 11 13 15 17 19 21
23 25 27 29 31 33 35 37 39
W3sicHJvYmxlbV9pZCI6IjEwNDM1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViOWNjXHVjZTdjXHViNzdjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI5Y2NcdWNlN2NcdWI3N2NcdWIyOTQgXHViY2Y0XHViNGRjIFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWQ1NWMgXHVjODg1XHViOTU4XHViODVjLCBcdWM1ZWNcdWI3ZWMgXHViY2MwXHVkNjE1IFx1ZDMxMFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YWMwNFx1YjJlOFx1ZDU1YyBcdWM4ODVcdWI5NThcdWM3NzggMVx1Yzc3OFx1YzZhOSBcdWI5Y2NcdWNlN2NcdWI3N2MgXHVhYzhjXHVjNzg0IFRjaG91a2FpbGxvblx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjMGI0XHVkM2I0XHViY2ZjIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+VGNob3VrYWlsbG9uXHViMjk0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViZTQ4XHVjZTc4XHVhY2ZjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBSb3VtYmFcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmNmNFx1YjRkYyBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjOWM0XHVkNTg5XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIHNyYz1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3VwbG9hZFwvaW1hZ2VzMlwvbWFuY2FsYS5wbmdcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZFx1Yzc1OCBcdWJlNDhcdWNlNzhcdWM3NDAgUm91bWJhXHVjNzc0XHViYTcwLCBcdWNjOThcdWM3NGNcdWM1ZDQgXHVkNTZkXHVjMGMxIFx1YmU0NFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWQwZGNcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MWNcdWIyZTQuIFx1YzZiMFx1YzEyMCwgXHVhYzAxIFx1Y2U3OFx1Yzc0NCBCW05dXHVjNzc0XHViNzdjIFx1ZDU2MCBcdWI1NGMsIEJbTl1cdWM1ZDAgTlx1YWMxY1x1Yzc1OCBcdWFkNmNcdWMyYWNcdWM3NzQgXHViNGU0XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NDQgXHVjYzNlXHViMjk0XHViMmU0LiBcdWFkZjhcdWI3ZjAgXHVjZTc4XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWI3N2NcdWJhNzQgXHVjNTQ0XHViYjM0IFx1YWM4M1x1Yzc3NFx1YjA5OCBcdWMxMjBcdWQwZGRcdWQ1NzRcdWIzYzQgXHVjMGMxXHVhZDAwXHVjNWM2XHViMmU0LiBcdWI5Y2NcdWM3N2MgQltOXT1OXHVjNzc4IFx1Y2U3OFx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzQgXHVhZGY4IFx1ZDMxMFx1Yzc0MCBcdWQzMjhcdWJjMzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgXHViOWU4IFx1Y2NhYiBcdWM5MDRcdWM3NDQgXHViY2Y0XHViYTc0IFx1YjQxY1x1YjJlNC4gM1x1YmM4OCBcdWNlNzhcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTVjIFx1YzBjMVx1ZDY2OVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1YWNlMFx1Yjk3OCBcdWNlNzhcdWM3NTggXHVhZDZjXHVjMmFjXHVjNzQ0IFJvdW1iYVx1YzY0MCBCWzFdLCBCWzJdLCAuLi4gLCBCW04tMV1cdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YWNlMFx1Yjk3NFx1YWM4YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM5MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWMyZGNcdWQ1ODlcdWM3NDQgXHVhY2M0XHVjMThkIFx1YmMxOFx1YmNmNVx1ZDU1OFx1YzVlYyBcdWJhYThcdWI0ZTAgXHVhZDZjXHVjMmFjXHVjNzc0IFJvdW1iYVx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDRcdWIyZTRcdWJhNzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzEzMVx1YWNmNVx1YzgwMVx1YzczY1x1Yjg1YyBcdWI5YzhcdWNlNThcdWFjOGMgXHViNDE4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHVjNzc0XHVjYzk4XHViN2ZjIFx1YzEzMVx1YWNmNVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYWE4XHViNGUwIFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc0NCBcdWMyYjlcdWI5YWNcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYWE4XHViNGUwIFx1YzgxNVx1YzIxOCBOXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVhZDZjXHVjMmFjXHVjNzc0IFx1Y2QxZCBOXHVhYzFjXHVjNzdjIFx1YjU0Y1x1Yzc1OCBcdWMyYjlcdWI5YWNcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWM3MjBcdWM3N2NcdWQ1NThcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM3MDRcdWM1ZDBcdWMxMWNcdWM3NTggUm91bWJhXHViOTdjIFx1YmU4MCBcdWJjZjRcdWI0ZGNcdWQzMTBcdWM3NTggXHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkYyB7IDAsIDEsIDMgfSBcdWM3NDAgXHVhZDZjXHVjMmFjXHVjNzc0IDRcdWFjMWNcdWM3N2MgXHViNTRjXHVjNzU4IFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWMyYjlcdWI5YWNcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkMWQgXHVhZDZjXHVjMmFjXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCBcdWMyYjlcdWI5YWNcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUCAmbGU7IDEwMDApPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViYzg4XHVkNjM4IFRcdWM2NDAgXHViY2Y0XHViNGRjXHVkMzEwXHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWFkNmNcdWMyYWNcdWM3NTggXHVjZDFkIFx1YWMxY1x1YzIxOCBOXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOCBUXHVjNjQwIFx1YWQ2Y1x1YzJhY1x1Yzc3NCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxIFx1YjJmNFx1YWNhOCBcdWM3ODhcdWIyOTQgXHViY2Y0XHViNGRjXHVkMzEwXHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM3MDRcdWNlNTggQlx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWQ2YzQgXHVjMmI5XHViOWFjXHVkNTU4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgQlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHViMjk0XHViMzcwLCBcdWMyMThcdWIyOTQgMTBcdWFjMWMgXHViMmU4XHVjNzA0XHViODVjIFx1YjA0YVx1YzViNFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YzExYyBCXHViMjk0IDgwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTA0MzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYW5jYWxhIiwiZGVzY3JpcHRpb24iOiI8cD5NYW5jYWxhIGlzIGEgZmFtaWx5IG9mIGJvYXJkIGdhbWVzIHBsYXllZCBhcm91bmQgdGhlIHdvcmxkLCBzb21ldGltZXMgY2FsbGVkIHNvd2luZyBnYW1lcywgb3IgY291bnQtYW5kLWNhcHR1cmUgZ2FtZXMsIHdoaWNoIGRlc2NyaWJlcyB0aGUgZ2FtZSBwbGF5LiBPbmUgc2ltcGxlIHZhcmlhbnQgaXMgYSBzb2xpdGFpcmUgZ2FtZSBjYWxsZWQgVGNob3VrYWlsbG9uIHdoaWNoIHdhcyBkZXNjcmliZWQgYnkgViZlYWN1dGU7cm9uaXF1ZSBHYXV0aGVyb24uIFRjaG91a2FpbGxvbiBpcyBwbGF5ZWQgb24gYSBib2FyZCByZXNwZWN0aXZlbHkgYW5kIGFuIGV4dHJhIGVtcHR5IGJpbiBjYWxsZWQgUm91bWJhIG9uIHRoZSBsZWZ0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9tYW5jYWxhLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjM3NnB4OyB3aWR0aDo0ODVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BIHNpbmdsZSBwbGF5IGNvbnNpc3RzIG9uIGNob29zaW5nIGEgYmluLCBuLCBmb3Igd2hpY2ggYltuXSA9IG4gKGluZGljYXRlZCBieSB0aGUgZGFya2VyIGNpcmNsZXMgaW4gdGhlIGRpYWdyYW0pIGFuZCBkaXN0cmlidXRpbmcgdGhlIGNvdW50ZXJzIG9uZSBwZXIgYmluIHRvIHRoZSBiaW5zIHRvIHRoZSBsZWZ0IGluY2x1ZGluZyB0aGUgUm91bWJhIChnZXR0aW5nIHRoZSBuZXh0IGRpYWdyYW0gYmVsb3cgaW4gdGhlIGZpZ3VyZSBhYm92ZSkuIElmIHRoZXJlIGlzIG5vIGJpbiB3aGVyZSBiW25dID0gbiwgdGhlbiB0aGUgYm9hcmQgaXMgYSBsb3NpbmcgYm9hcmQuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGlzIGEgc2VxdWVuY2Ugb2YgcGxheXMgd2hpY2ggdGFrZXMgdGhlIGluaXRpYWwgYm9hcmQgZGlzdHJpYnV0aW9uIHRvIG9uZSBpbiB3aGljaCBldmVyeSBjb3VudGVyIGlzIGluIHRoZSBSb3VtYmEsIHRoZSBpbml0aWFsIGRpc3RyaWJ1dGlvbiBpcyBjYWxsZWQgYSB3aW5uYWJsZSBib2FyZC4gSW4gdGhlIGV4YW1wbGUgYWJvdmUsIDAsIDEsIDMsIC4uLiBpcyBhIHdpbm5hYmxlIGJvYXJkICh0aGUgJnF1b3Q7Li4uJnF1b3Q7IGluZGljYXRlcyBhbGwgdGhlIGJpbnMgdG8gdGhlIHJpZ2h0IG9mIGJpbiAzIGNvbnRhaW4gMCkuIEZvciBlYWNoIHRvdGFsIG51bWJlciBvZiBjb3VudGVycywgdGhlcmUgaXMgYSB1bmlxdWUgZGlzdHJpYnV0aW9uIG9mIHRoZSBjb3VudGVycyB0byBiaW5zIHRvIG1ha2UgYSB3aW5uYWJsZSBib2FyZCBmb3IgdGhhdCB0b3RhbCBjb3VudCAoc28gMCwgMSwgMywgLi4uIGlzIHRoZSBvbmx5IHdpbm5hYmxlIGJvYXJkIHdpdGggNCBjb3VudGVycykuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCBmaW5kcyB0aGUgd2lubmFibGUgYm9hcmQgZm9yIGEgdG90YWwgY291bnQgaW5wdXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBzaG91bGQgYmUgcHJvY2Vzc2VkIGlkZW50aWNhbGx5IGFuZCBpbmRlcGVuZGVudGx5LjxcL3A+XHJcblxyXG48cD5FYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgb2YgaW5wdXQuIEl0IGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIsIEssIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlLCBmb2xsb3dlZCBieSB0aGUgdG90YWwgY291bnQgTiAoMSAmbGU7IE4gJmxlOyAyMDAwKSBvZiB0aGUgd2lubmFibGUgYm9hcmQgdG8gYmUgZm91bmQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgd2lsbCBiZSBtdWx0aXBsZSBsaW5lcyBvZiBvdXRwdXQuIFRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyLCBLLCBmb2xsb3dlZCBieSBhIHNpbmdsZSBzcGFjZSwgZm9sbG93ZWQgYnkgdGhlIGluZGV4IG9mIHRoZSBsYXN0IGJpbiwgQiwgd2l0aCBhIG5vbi16ZXJvIGNvdW50LiBJbnB1dCB3aWxsIGJlIGNob3NlbiBzbyB0aGF0IEIgd2lsbCBiZSBubyBtb3JlIHRoYW4gODAuIFRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBmb3IgZWFjaCBkYXRhc2V0IGlzIGZvbGxvd2VkIGJ5IHRoZSBiaW4gY291bnRzIGJbMV0sIGJbMl0sIC4uLiwgYltCXSwgMTAgcGVyIGxpbmUgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==