시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB57738631367.024%

문제

홍준 왕국의 국왕 홍준이는 자신을 호위하는 N명의 친위대 병사가 있다. 병사들의 키는 모두 다르다. 홍준이는 그들을 일렬로 세울 때, 키 순서대로 세우는 것보다 맨 끝 두 병사를 제외한 나머지 병사들의 양 옆 두 병사의 키가 자신 보다 크거나 모두 자신보다 작을 때 보기 좋다고 생각한다. 예를 들어, 홍준이에게 7명의 친위대 병사가 있고, 그 들의 키가 160, 162, 164, 166, 168, 170, 그리고 172cm 라고 하자. 아래와 같이 병사가 일렬로 서있으면 홍준이는 보기 좋다고 생각한다.

만약 홍준이가 매일 같은 병사 배치를 본다면 매우 지루해할 것이다. 때문에 매일 병사들의 배치를 새롭게 하고 싶다. 즉, 병사 N명이 있을 때 서로 다른 배치가 몇 가지 있는지 알고 싶어한다.

예를 들어, 병사가 4명이 있고 편의상 그들의 키를 1, 2, 3, 4라고 나타내자. 그러면 아래와 같이 10가지 배치가 가능하다.

1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423

병사의 수 N이 주어졌을 때, 가능한 배치의 수를 구하는 프로그램을 작성하자.

입력

첫 줄에 테스트케이스 수 T가 주어진다. (1 ≤ T ≤ 1,000)

각 테스트케이스마다 병사의 수를 나타내는 자연수 N이 주어진다. (1 ≤ N ≤ 20)

출력

각 테스트케이스 마다 가능한 배치의 수를 줄로 구분하여 출력한다.

예제 입력 1

4
1
3
4
20

예제 출력 1

1
4
10
740742376475050
W3sicHJvYmxlbV9pZCI6IjM5NDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2NGRcdWM5MDBcdWM3NzRcdWM3NTggXHVjZTVjXHVjNzA0XHViMzAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2NGRcdWM5MDAgXHVjNjU1XHVhZDZkXHVjNzU4IFx1YWQ2ZFx1YzY1NSBcdWQ2NGRcdWM5MDBcdWM3NzRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzQ0IFx1ZDYzOFx1YzcwNFx1ZDU1OFx1YjI5NCBOXHViYTg1XHVjNzU4IFx1Y2U1Y1x1YzcwNFx1YjMwMCBcdWJjZDFcdWMwYWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWJjZDFcdWMwYWNcdWI0ZTRcdWM3NTggXHVkMGE0XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5NzRcdWIyZTQuIFx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YjI5NCBcdWFkZjhcdWI0ZTRcdWM3NDQgXHVjNzdjXHViODJjXHViODVjIFx1YzEzOFx1YzZiOCBcdWI1NGMsIFx1ZDBhNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjMTM4XHVjNmIwXHViMjk0IFx1YWM4M1x1YmNmNFx1YjJlNCBcdWI5ZTggXHViMDVkIFx1YjQ1MCBcdWJjZDFcdWMwYWNcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIFx1YjA5OFx1YmEzOFx1YzljMCBcdWJjZDFcdWMwYWNcdWI0ZTRcdWM3NTggXHVjNTkxIFx1YzYwNiBcdWI0NTAmbmJzcDtcdWJjZDFcdWMwYWNcdWM3NTgmbmJzcDtcdWQwYTRcdWFjMDAgXHVjNzkwXHVjMmUwIFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHViYWE4XHViNDUwIFx1Yzc5MFx1YzJlMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDQgXHViNTRjIFx1YmNmNFx1YWUzMCBcdWM4OGJcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQ2NGRcdWM5MDBcdWM3NzRcdWM1ZDBcdWFjOGMgN1x1YmE4NVx1Yzc1OCBcdWNlNWNcdWM3MDRcdWIzMDAgXHViY2QxXHVjMGFjXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVhZGY4IFx1YjRlNFx1Yzc1OCBcdWQwYTRcdWFjMDAgMTYwLCAxNjIsIDE2NCwgMTY2LCAxNjgsIDE3MCwgXHVhZGY4XHViOWFjXHVhY2UwIDE3MmNtIFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViY2QxXHVjMGFjXHVhYzAwIFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWMxMWNcdWM3ODhcdWM3M2NcdWJhNzQgXHVkNjRkXHVjOTAwXHVjNzc0XHViMjk0IFx1YmNmNFx1YWUzMCBcdWM4OGJcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2t1ZDEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTIzcHg7IHdpZHRoOjM1OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva3VkMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzlweDsgd2lkdGg6MzY2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YWMwMCBcdWI5ZTRcdWM3N2MgXHVhYzE5XHVjNzQwIFx1YmNkMVx1YzBhYyZuYnNwO1x1YmMzMFx1Y2U1OFx1Yjk3YyBcdWJjZjhcdWIyZTRcdWJhNzQgXHViOWU0XHVjNmIwIFx1YzljMFx1YjhlOFx1ZDU3NFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWI5ZTRcdWM3N2MgXHViY2QxXHVjMGFjXHViNGU0XHVjNzU4IFx1YmMzMFx1Y2U1OFx1Yjk3YyBcdWMwYzhcdWI4NmRcdWFjOGMgXHVkNTU4XHVhY2UwIFx1YzJmNlx1YjJlNC4gXHVjOTg5LCZuYnNwO1x1YmNkMVx1YzBhYyBOXHViYTg1XHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGMgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJjMzBcdWNlNThcdWFjMDAgXHViYTg3IFx1YWMwMFx1YzljMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNTRjXHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViY2QxXHVjMGFjXHVhYzAwIDRcdWJhODVcdWM3NzQgXHVjNzg4XHVhY2UwIFx1ZDNiOFx1Yzc1OFx1YzBjMSBcdWFkZjhcdWI0ZTRcdWM3NTggXHVkMGE0XHViOTdjIDEsIDIsIDMsIDRcdWI3N2NcdWFjZTAgXHViMDk4XHVkMGMwXHViMGI0XHVjNzkwLiBcdWFkZjhcdWI3ZWNcdWJhNzQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCAxMFx1YWMwMFx1YzljMCBcdWJjMzBcdWNlNThcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD4xMzI0LCAyMTQzLCAzMTQyLCAyMzE0LCAzNDEyLCA0MjMxLCA0MTMyLCAyNDEzLCAzMjQxLCAxNDIzPFwvcD5cclxuXHJcbjxwPlx1YmNkMVx1YzBhY1x1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYzMwXHVjZTU4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEmbmJzcDsmbGU7IFQmbmJzcDsmbGU7IDEsMDAwKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YmNkMVx1YzBhY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEmbmJzcDsmbGU7IE4mbmJzcDsmbGU7IDIwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJjMzBcdWNlNThcdWM3NTggXHVjMjE4XHViOTdjIFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM5NDgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgS2luZydzIFVwcyBhbmQgRG93bnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBraW5nIGhhcyBndWFyZHMgb2YgYWxsIGRpZmZlcmVudCBoZWlnaHRzLiBSYXRoZXIgdGhhbiBsaW5lIHRoZW0gdXAgaW4gaW5jcmVhc2luZyBvciBkZWNyZWFzaW5nIGhlaWdodCBvcmRlciwgaGUgd2FudHMgdG8gbGluZSB0aGVtIHVwIHNvIGVhY2ggZ3VhcmQgaXMgZWl0aGVyIHNob3J0ZXIgdGhhbiB0aGUgZ3VhcmRzIG5leHQgdG8gaGltIG9yIHRhbGxlciB0aGFuIHRoZSBndWFyZHMgbmV4dCB0byBoaW0gKHNvIHRoZSBoZWlnaHRzIGdvIHVwIGFuZCBkb3duIGFsb25nIHRoZSBsaW5lKS4gRm9yIGV4YW1wbGUsIHNldmVuIGd1YXJkcyBvZiBoZWlnaHRzIDE2MCwgMTYyLCAxNjQsIDE2NiwgMTY4LCAxNzAgYW5kIDE3MiBjbS4gY291bGQgYmUgYXJyYW5nZWQgYXM6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva3VkMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjNweDsgd2lkdGg6MzU4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+b3IgcGVyaGFwczo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rdWQyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzOXB4OyB3aWR0aDozNjZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUga2luZyB3YW50cyB0byBrbm93IGhvdyBtYW55IGd1YXJkcyBoZSBuZWVkcyBzbyBoZSBjYW4gaGF2ZSBhIGRpZmZlcmVudCB1cCBhbmQgZG93biBvcmRlciBhdCBlYWNoIGNoYW5naW5nIG9mIHRoZSBndWFyZCBmb3IgcmVzdCBvZiBoaXMgcmVpZ24uIFRvIGJlIGFibGUgdG8gZG8gdGhpcywgaGUgbmVlZHMgdG8ga25vdyBmb3IgYSBnaXZlbiBudW1iZXIgb2YgZ3VhcmRzLCBuLCBob3cgbWFueSBkaWZmZXJlbnQgdXAgYW5kIGRvd24gb3JkZXJzIHRoZXJlIGFyZTo8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIHRoZXJlIGFyZSBmb3VyIGd1YXJkczogMSwgMiwgMywgNCBjYW4gYmUgYXJyYW5nZWQgYXM6PFwvcD5cclxuXHJcbjxwPjEzMjQsIDIxNDMsIDMxNDIsIDIzMTQsIDM0MTIsIDQyMzEsIDQxMzIsIDI0MTMsIDMyNDEsIDE0MjM8XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgdGFrZXMgYXMgaW5wdXQgYSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIHRoZSBudW1iZXIgb2YgZ3VhcmRzIGFuZCByZXR1cm5zIHRoZSBudW1iZXIgb2YgdXAgYW5kIGRvd24gb3JkZXJzIGZvciBuIGd1YXJkcyBvZiBkaWZmZXJpbmcgaGVpZ2h0cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIHNpbmdsZSBsaW5lIG9mIGlucHV0IGNvbnRhaW5pbmcgb25lIGludGVnZXIsIG4gKDEgJmx0Oz0gbiAmbHQ7PSAyMCksIGlzIHRoZSBudW1iZXIgb2YgZ3VhcmRzIG9mIGRpZmZlcmluZyBoZWlnaHRzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIG9uZSBsaW5lIG9mIG91dHB1dC4gSXQgY29udGFpbnMgdGhlIG51bWJlciBvZiB1cCBhbmQgZG93biBvcmRlcnMgZm9yIHRoZSBuIGd1YXJkcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d