시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IFx1YjJlOFx1YzcwNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMGMwXHVjNzdjKFx1YWMwMFx1Yjg1YyBcdWMxMzhcdWI4NWMgXHVhZTM4XHVjNzc0XHVhYzAwIDFcdWM3NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDBjMFx1Yzc3YylcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWIzYzRcdWQ2MTVcdWM3NDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LiBcdWFjMTVcdWMwYjBcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDBjMFx1Yzc3Y1x1Yzc0NCBcdWIwYThcdWFlNDBcdWM1YzZcdWM3NzQgXHViYzMwXHVjZTU4XHVkNTc0XHVjMTFjIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1Yzg4NVx1Yjk1OFx1Yjk3YyBcdWJhODcgXHVhYzAwXHVjOWMwXHViMDk4IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3NwYW4+PFwvcD5cclxuXHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWIyZThcdWM3MDQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDBjMFx1Yzc3Y1x1Yzc0NCA2XHVhYzFjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWI0NTAgXHVjODg1XHViOTU4XHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSAxeDYgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVhY2ZjIDJ4MyBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUoNngxXHVjNzQwIDF4Nlx1YWNmYyBcdWFjMTlcdWFjZTAsIDJ4M1x1Yzc0MCAzeDJcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YWM4M1x1YzczY1x1Yjg1YyBcdWNlNWNcdWIyZTQpXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg3XHViMmU0LiBcdWI2MTBcdWQ1NWMsIDRcdWFjMWMgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWIyOTQgMXg0XHVjNjQwIDJ4MiwgXHVjZDFkIFx1YjQ1MCBcdWM4ODVcdWI5NThcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWIzYzQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YWUzMCBcdWI1NGNcdWJiMzgpPFwvcD5cclxuXHJcblxyXG48cD5OXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YzgxNVx1ZDY1NVx1ZDc4OCBOXHVjODg1XHViOTU4XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YjJlOFx1YzcwNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMGMwXHVjNzdjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjljY1x1YzU3ZCBOPTJcdWM3NzggXHVhY2JkXHVjNmIwIFx1YjJmNVx1Yzc0MCA0XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IE4oMSAmbGU7IE4gJmxlOyA3NSlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM4MTVcdWQ2NTVcdWQ3ODggTlx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWIyZThcdWM3MDQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDBjMFx1Yzc3Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJjMThcdWI0ZGNcdWMyZGMgXHViYWE4XHViNGUwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWQwYzBcdWM3N2NcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgTlx1YWMxY1x1YmNmNFx1YjJlNCBcdWIzNTQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiBcdWIyZjVcdWM3NDAgXHVkNTZkXHVjMGMxIDEwPHN1cD4xODxcL3N1cD5cdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MDgzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmxvb3JpbmcgVGlsZXMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSB3YW50IHRvIGRlY29yYXRlIHlvdXIgZmxvb3Igd2l0aCBzcXVhcmUgdGlsZXMuIFlvdSBsaWtlIHJlY3RhbmdsZXMuIFdpdGggc2l4IHNxdWFyZSBmbG9vcmluZyB0aWxlcywgeW91IGNhbiBmb3JtIGV4YWN0bHkgdHdvIHVuaXF1ZSByZWN0YW5nbGVzIHRoYXQgdXNlIGFsbCBvZiB0aGUgdGlsZXM6IDF4NiwgYW5kIDJ4MyAoNngxIGlzIGNvbnNpZGVyZWQgdGhlIHNhbWUgYXMgMXg2LiBMaWtld2lzZSwgM3gyIGlzIHRoZSBzYW1lIGFzIDJ4MykuIFlvdSBjYW4gYWxzbyBmb3JtIGV4YWN0bHkgdHdvIHVuaXF1ZSByZWN0YW5nbGVzIHdpdGggZm91ciBzcXVhcmUgdGlsZXMsIHVzaW5nIGFsbCBvZiB0aGUgdGlsZXM6IDF4NCwgYW5kIDJ4Mi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gYW4gaW50ZWdlciBOLCB3aGF0IGlzIHRoZSBzbWFsbGVzdCBudW1iZXIgb2Ygc3F1YXJlIHRpbGVzIG5lZWRlZCB0byBiZSBhYmxlIHRvIG1ha2UgZXhhY3RseSBOIHVuaXF1ZSByZWN0YW5nbGVzLCBhbmQgbm8gbW9yZSwgdXNpbmcgYWxsIG9mIHRoZSB0aWxlcz8gSWYgTj0yLCB0aGUgYW5zd2VyIGlzIDQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSB3aWxsIGJlIHNldmVyYWwgdGVzdCBjYXNlcyBpbiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHdpbGwgY29uc2lzdCBvZiBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDc1KSwgd2hpY2ggcmVwcmVzZW50cyB0aGUgbnVtYmVyIG9mIGRlc2lyZWQgcmVjdGFuZ2xlcy4gVGhlIGlucHV0IHdpbGwgZW5kIHdpdGggYSBsaW5lIHdpdGggYSBzaW5nbGUgMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIG9uIGl0cyBvd24gbGluZSwgcmVwcmVzZW50aW5nIHRoZSBzbWFsbGVzdCBudW1iZXIgb2Ygc3F1YXJlIGZsb29yaW5nIHRpbGVzIG5lZWRlZCB0byBiZSBhYmxlIHRvIGZvcm0gZXhhY3RseSBOIHJlY3RhbmdsZXMsIGFuZCBubyBtb3JlLCB1c2luZyBhbGwgb2YgdGhlIHRpbGVzLiBUaGUgYW5zd2VyIGlzIGd1YXJhbnRlZWQgdG8gYmUgYXQgbW9zdCAxMDxzdXA+MTg8XC9zdXA+LiBPdXRwdXQgbm8gZXh0cmEgc3BhY2VzLCBhbmQgZG8gbm90IHNlcGFyYXRlIGFuc3dlcnMgd2l0aCBibGFuayBsaW5lcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=