시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 13 5 5 50.000%

문제

강산이는 단위 정사각형 타일(가로 세로 길이가 1인 정사각형 타일)을 좋아한다. 하지만, 좋아하는 도형은 직사각형이다. 강산이는 모든 타일을 남김없이 배치해서 직사각형을 만들고 한다. 이 때, 서로 다른 직사각형 종류를 몇 가지나 만들 수 있을까?

예를 들어, 단위 정사각형 타일을 6개 가지고 있을 때, 두 종류의 직사각형 1x6 직사각형과 2x3 직사각형(6x1은 1x6과 같고, 2x3은 3x2와 같은 것으로 친다)을 만들 수 잇다. 또한, 4개 가지고 있을 때는 1x4와 2x2, 총 두 종류를 만들 수 있다. (정사각형도 직사각형에 포함되기 때문)

N이 주어졌을 때, 서로 다른 직사각형 정확히 N종류를 만들기 위해 필요한 단위 정사각형 타일의 개수의 최소값을 구하는 프로그램을 작성하시오. 만약 N=2인 경우 답은 4이다.

입력

입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄에 하나씩 N(1 ≤ N ≤ 75)이 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 정확히 N종류의 서로 다른 직사각형을 만들기 위해서 필요한 단위 정사각형 타일의 개수를 출력한다. 반드시 모든 정사각형 타일을 이용해야 하고, N개보다 더 만들 수 있으면 안된다. 답은 항상 1018을 넘지 않는다.

예제 입력 1

2
16
19
0

예제 출력 1

4
840
786432
W3sicHJvYmxlbV9pZCI6IjQwODMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViOWNjXHViNGU0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD48c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+XHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IFx1YjJlOFx1YzcwNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMGMwXHVjNzdjKFx1YWMwMFx1Yjg1YyBcdWMxMzhcdWI4NWMgXHVhZTM4XHVjNzc0XHVhYzAwIDFcdWM3NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDBjMFx1Yzc3YylcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWIzYzRcdWQ2MTVcdWM3NDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LiBcdWFjMTVcdWMwYjBcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDBjMFx1Yzc3Y1x1Yzc0NCBcdWIwYThcdWFlNDBcdWM1YzZcdWM3NzQgXHViYzMwXHVjZTU4XHVkNTc0XHVjMTFjIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM4ODVcdWI5NThcdWI5N2MgXHViYTg3IFx1YWMwMFx1YzljMFx1YjA5OCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9zcGFuPjxcL3A+XHJcblxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViMmU4XHVjNzA0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWQwYzBcdWM3N2NcdWM3NDQgNlx1YWMxYyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgMXg2IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YWNmYyAyeDMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1KDZ4MVx1Yzc0MCAxeDZcdWFjZmMgXHVhYzE5XHVhY2UwLCAyeDNcdWM3NDAgM3gyXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjODNcdWM3M2NcdWI4NWMgXHVjZTVjXHViMmU0KVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4N1x1YjJlNC4gXHViNjEwXHVkNTVjLCA0XHVhYzFjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM3NDQgXHViNTRjXHViMjk0IDF4NFx1YzY0MCAyeDIsIFx1Y2QxZCBcdWI0NTAgXHVjODg1XHViOTU4XHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiAoXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHViM2M0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWFlMzAgXHViNTRjXHViYjM4KTxcL3A+XHJcblxyXG5cclxuPHA+Tlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM4MTVcdWQ2NTVcdWQ3ODggTlx1Yzg4NVx1Yjk1OFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWIyZThcdWM3MDQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI5Y2NcdWM1N2QgTj0yXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWIyZjVcdWM3NDAgNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBOKDEgJmxlOyBOICZsZTsgNzUpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjODE1XHVkNjU1XHVkNzg4IE5cdWM4ODVcdWI5NThcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViMmU4XHVjNzA0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWQwYzBcdWM3N2NcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViYzE4XHViNGRjXHVjMmRjIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMGMwXHVjNzdjXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIE5cdWFjMWNcdWJjZjRcdWIyZTQgXHViMzU0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC4gXHViMmY1XHVjNzQwIFx1ZDU2ZFx1YzBjMSAxMDxzdXA+MTg8XC9zdXA+XHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDA4MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZsb29yaW5nIFRpbGVzIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3Ugd2FudCB0byBkZWNvcmF0ZSB5b3VyIGZsb29yIHdpdGggc3F1YXJlIHRpbGVzLiBZb3UgbGlrZSByZWN0YW5nbGVzLiBXaXRoIHNpeCBzcXVhcmUgZmxvb3JpbmcgdGlsZXMsIHlvdSBjYW4gZm9ybSBleGFjdGx5IHR3byB1bmlxdWUgcmVjdGFuZ2xlcyB0aGF0IHVzZSBhbGwgb2YgdGhlIHRpbGVzOiAxeDYsIGFuZCAyeDMgKDZ4MSBpcyBjb25zaWRlcmVkIHRoZSBzYW1lIGFzIDF4Ni4gTGlrZXdpc2UsIDN4MiBpcyB0aGUgc2FtZSBhcyAyeDMpLiBZb3UgY2FuIGFsc28gZm9ybSBleGFjdGx5IHR3byB1bmlxdWUgcmVjdGFuZ2xlcyB3aXRoIGZvdXIgc3F1YXJlIHRpbGVzLCB1c2luZyBhbGwgb2YgdGhlIHRpbGVzOiAxeDQsIGFuZCAyeDIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIGFuIGludGVnZXIgTiwgd2hhdCBpcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHNxdWFyZSB0aWxlcyBuZWVkZWQgdG8gYmUgYWJsZSB0byBtYWtlIGV4YWN0bHkgTiB1bmlxdWUgcmVjdGFuZ2xlcywgYW5kIG5vIG1vcmUsIHVzaW5nIGFsbCBvZiB0aGUgdGlsZXM/IElmIE49MiwgdGhlIGFuc3dlciBpcyA0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBzZXZlcmFsIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSB3aWxsIGNvbnNpc3Qgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyA3NSksIHdoaWNoIHJlcHJlc2VudHMgdGhlIG51bWJlciBvZiBkZXNpcmVkIHJlY3RhbmdsZXMuIFRoZSBpbnB1dCB3aWxsIGVuZCB3aXRoIGEgbGluZSB3aXRoIGEgc2luZ2xlIDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBzaW5nbGUgaW50ZWdlciBvbiBpdHMgb3duIGxpbmUsIHJlcHJlc2VudGluZyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHNxdWFyZSBmbG9vcmluZyB0aWxlcyBuZWVkZWQgdG8gYmUgYWJsZSB0byBmb3JtIGV4YWN0bHkgTiByZWN0YW5nbGVzLCBhbmQgbm8gbW9yZSwgdXNpbmcgYWxsIG9mIHRoZSB0aWxlcy4gVGhlIGFuc3dlciBpcyBndWFyYW50ZWVkIHRvIGJlIGF0IG1vc3QgMTA8c3VwPjE4PFwvc3VwPi4gT3V0cHV0IG5vIGV4dHJhIHNwYWNlcywgYW5kIGRvIG5vdCBzZXBhcmF0ZSBhbnN3ZXJzIHdpdGggYmxhbmsgbGluZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d