시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 49 32 28 71.795%

문제

상근이는 오른쪽 그림과 같은 미로에 갇혀있다. 미로는 육각형 모양의 방이 계속해서 붙어있는 모양이고, 이러한 방은 무수히 많이 있다. 또, 인접한 방은 문으로 연결되어 있어서, 한 방에서 다른 방으로 건너갈 수 있다. 하지만, 방의 개수는 무한대이기 때문에, 상근이는 절대 이 미로를 빠져나갈 수 없다.

오른쪽 그림에 상근이가 있는 방이 표시되어 있다. 이 때, 상근이가 있는 방에서 시작해서 방을 n번 이동해서, 다시 원래 있던 방으로 돌아오는 경로의 수를 구하려고 한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 n을 포함하는 한 줄로 이루어져 있다. (1 ≤ n ≤ 14)

출력

각 테스트 케이스에 대해서, 입력으로 주어진 n에 해당하는 경로의 개수를 출력한다. 정답은 항상 231보다 작다.

예제 입력 1

2
2
4

예제 출력 1

6
90
W3sicHJvYmxlbV9pZCI6IjUwNjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiZjhcdWI4NWNcdWM1ZDAgXHVhYzA3XHVkNzhjIFx1YzBjMVx1YWRmYyIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oZXgucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjI5MnB4OyB3aWR0aDoyNjhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYmY4XHViODVjXHVjNWQwIFx1YWMwN1x1ZDYwMFx1Yzc4OFx1YjJlNC4gXHViYmY4XHViODVjXHViMjk0IFx1YzcyMVx1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NTggXHViYzI5XHVjNzc0IFx1YWNjNFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyOTQgXHViYWE4XHVjNTkxXHVjNzc0XHVhY2UwLCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViYzI5XHVjNzQwIFx1YmIzNFx1YzIxOFx1ZDc4OCBcdWI5Y2VcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJjMjlcdWM3NDAgXHViYjM4XHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWMxMWMsIFx1ZDU1YyBcdWJjMjlcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1YmMyOVx1YzczY1x1Yjg1YyBcdWFjNzRcdWIxMDhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWJjMjlcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1YmIzNFx1ZDU1Y1x1YjMwMFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MDhcdWIzMDAgXHVjNzc0IFx1YmJmOFx1Yjg1Y1x1Yjk3YyBcdWJlNjBcdWM4MzhcdWIwOThcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc3NCBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzg4XHViMjk0IFx1YmMyOVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMgXHViYzI5XHVjNzQ0IG5cdWJjODggXHVjNzc0XHViM2Q5XHVkNTc0XHVjMTFjLCZuYnNwO1x1YjJlNFx1YzJkYyBcdWM2ZDBcdWI3OTggXHVjNzg4XHViMzU4IFx1YmMyOVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgblx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxNCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgblx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1Yzc0MCBcdWQ1NmRcdWMwYzEgMjxzdXA+MzE8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MDY5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSG9uZXljb21iIFdhbGsiLCJkZXNjcmlwdGlvbiI6IjxwPkEgYmVlIGxhcnZhIGxpdmluZyBpbiBhIGhleGFnb25hbCBjZWxsIG9mIGEgbGFyZ2UgaG9uZXljb21iIGRlY2lkZXMgdG8gY3JlZXAgZm9yIGEgd2Fsay4gSW4gZWFjaCAmbGRxdW87c3RlcCZyZHF1bzsgdGhlIGxhcnZhIG1heSBtb3ZlIGludG8gYW55IG9mIHRoZSBzaXggYWRqYWNlbnQgY2VsbHMgYW5kIGFmdGVyIG4gc3RlcHMsIGl0IGlzIHRvIGVuZCB1cCBpbiBpdHMgb3JpZ2luYWwgY2VsbC48XC9wPlxyXG5cclxuPHA+WW91ciBwcm9ncmFtIGhhcyB0byBjb21wdXRlLCBmb3IgYSBnaXZlbiBuLCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBzdWNoIGxhcnZhIHdhbGtzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBnaXZpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCBjYXNlIGNvbnNpc3RzIG9mIG9uZSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBuLCB3aGVyZSAxICZsZTsgbiAmbGU7IDE0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiB3YWxrcy4gVW5kZXIgdGhlIGFzc3VtcHRpb24gMSAmbGU7IG4gJmxlOyAxNCwgdGhlIGFuc3dlciB3aWxsIGJlIGxlc3MgdGhhbiAyPHN1cD4zMTxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d