문제
리처드 필립스 파인만은 노벨 물리학상을 수상한 미국의 물리학자이다. 그는 이론물리학을 연구했고, 양자 컴퓨팅 분야를 개척했다. "Surely You’re Joking, Mr. Feynman!", "What Do You Care What Other People Think?"와 같은 그의 책은 많은 사람들의 사랑을 받았고, 한국에도 번역되어 출판되어져 있다. 그는 오랜 기간동안 퍼즐, 자물쇠, 암호를 만들고 푸는 일에 중독되어 있었다.
어느 날, 남아메리카의 한 농장에서 파인먼의 것으로 추정되는 한 메모가 발견되었다. 퍼즐은 이 메모에는 중간자와 전자기에 대한 내용이 적혀있었고, 가장 마지막 줄에는 다음과 같은 퀴즈가 적혀져 있었다. "N × N 정사각형으로 이루어진 그리드에는 서로 다른 정사각형이 몇 개나 있을까요?" 이 퀴즈의 정답을 구하는 프로그램을 작성하시오.
N = 2인 경우에 정답은 5이다.
출력
각 테스트 케이스에 대해서, 한 줄에 하나씩 서로 다른 정사각형의 개수를 출력한다.
W3sicHJvYmxlbV9pZCI6IjU3MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWM3NzhcdWI5Y2MiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjlhY1x1Y2M5OFx1YjRkYyBcdWQ1NDRcdWI5YmRcdWMyYTQgXHVkMzBjXHVjNzc4XHViOWNjXHVjNzQwIFx1YjE3OFx1YmNhOCBcdWJiM2NcdWI5YWNcdWQ1NTlcdWMwYzFcdWM3NDQgXHVjMjE4XHVjMGMxXHVkNTVjIFx1YmJmOFx1YWQ2ZFx1Yzc1OCBcdWJiM2NcdWI5YWNcdWQ1NTlcdWM3OTBcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjI5NCBcdWM3NzRcdWI4NjBcdWJiM2NcdWI5YWNcdWQ1NTlcdWM3NDQgXHVjNWYwXHVhZDZjXHVkNTg4XHVhY2UwLCBcdWM1OTFcdWM3OTAgXHVjZWY0XHVkNGU4XHVkMzA1IFx1YmQ4NFx1YzU3Y1x1Yjk3YyBcdWFjMWNcdWNjOTlcdWQ1ODhcdWIyZTQuICZxdW90O1N1cmVseSBZb3UmcnNxdW87cmUgSm9raW5nLCBNci4gRmV5bm1hbiEmcXVvdDssICZxdW90O1doYXQgRG8gWW91IENhcmUgV2hhdCBPdGhlciBQZW9wbGUgVGhpbms/JnF1b3Q7XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFkZjhcdWM3NTggXHVjYzQ1XHVjNzQwIFx1YjljZVx1Yzc0MCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NTggXHVjMGFjXHViNzkxXHVjNzQ0IFx1YmMxYlx1YzU1OFx1YWNlMCwgXHVkNTVjXHVhZDZkXHVjNWQwXHViM2M0IFx1YmM4OFx1YzVlZFx1YjQxOFx1YzViNCBcdWNkOWNcdWQzMTBcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWIyOTQgXHVjNjI0XHViNzljIFx1YWUzMFx1YWMwNFx1YjNkOVx1YzU0OCBcdWQzN2NcdWM5OTAsIFx1Yzc5MFx1YmIzY1x1YzFlMCwgXHVjNTU0XHVkNjM4XHViOTdjIFx1YjljY1x1YjRlNFx1YWNlMCBcdWQ0NzhcdWIyOTQgXHVjNzdjXHVjNWQwIFx1YzkxMVx1YjNjNVx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YzhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjI5MCBcdWIwYTAsIFx1YjBhOFx1YzU0NFx1YmE1NFx1YjlhY1x1Y2U3NFx1Yzc1OCBcdWQ1NWMgXHViMThkXHVjN2E1XHVjNWQwXHVjMTFjIFx1ZDMwY1x1Yzc3OFx1YmEzY1x1Yzc1OCBcdWFjODNcdWM3M2NcdWI4NWMgXHVjZDk0XHVjODE1XHViNDE4XHViMjk0IFx1ZDU1YyBcdWJhNTRcdWJhYThcdWFjMDAgXHViYzFjXHVhY2FjXHViNDE4XHVjNWM4XHViMmU0LiBcdWQzN2NcdWM5OTBcdWM3NDAgXHVjNzc0IFx1YmE1NFx1YmFhOFx1YzVkMFx1YjI5NCBcdWM5MTFcdWFjMDRcdWM3OTBcdWM2NDAgXHVjODA0XHVjNzkwXHVhZTMwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIwYjRcdWM2YTlcdWM3NzQgXHVjODAxXHVkNjAwXHVjNzg4XHVjNWM4XHVhY2UwLCBcdWFjMDBcdWM3YTUgXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDAzNFx1Yzk4OFx1YWMwMCBcdWM4MDFcdWQ2MDBcdWM4MzggXHVjNzg4XHVjNWM4XHViMmU0LiAmcXVvdDtOICZ0aW1lczsgTiBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWRmOFx1YjlhY1x1YjRkY1x1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWJhODcgXHVhYzFjXHViMDk4IFx1Yzc4OFx1Yzc0NFx1YWU0Y1x1YzY5ND8mcXVvdDsgXHVjNzc0IFx1ZDAzNFx1Yzk4OFx1Yzc1OCBcdWM4MTVcdWIyZjVcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPk4gPSAyXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM4MTVcdWIyZjVcdWM3NDAgNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaG93bWFueXNxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjkzcHg7IHdpZHRoOjQzMnB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhZGY4XHViOWFjXHViNGRjIFx1ZDU1YyBcdWJjYzBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1NzI0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmV5bm1hbiIsImRlc2NyaXB0aW9uIjoiPHA+UmljaGFyZCBQaGlsbGlwcyBGZXlubWFuIHdhcyBhIHdlbGwga25vd24gQW1lcmljYW4gcGh5c2ljaXN0IGFuZCBhIHJlY2lwaWVudCBvZiB0aGUgTm9iZWwgUHJpemUgaW4gUGh5c2ljcy4gSGUgd29ya2VkIGluIHRoZW9yZXRpY2FsIHBoeXNpY3MgYW5kIGFsc28gcGlvbmVlcmVkIHRoZSBcdWZiMDFlbGQgb2YgcXVhbnR1bSBjb21wdXRpbmcuIEhlIHZpc2l0ZWQgU291dGggQW1lcmljYSBmb3IgdGVuIG1vbnRocywgZ2l2aW5nIGxlY3R1cmVzIGFuZCBlbmpveWluZyBsaWZlIGluIHRoZSB0cm9waWNzLiBIZSBpcyBhbHNvIGtub3duIGZvciBoaXMgYm9va3MgJmxkcXVvO1N1cmVseSBZb3UmcnNxdW87cmUgSm9raW5nLCBNci4gRmV5bm1hbiEmcmRxdW87IGFuZCAmbGRxdW87V2hhdCBEbyBZb3UgQ2FyZSBXaGF0IE90aGVyIFBlb3BsZSBUaGluaz8mcmRxdW87LCB3aGljaCBpbmNsdWRlIHNvbWUgb2YgaGlzIGFkdmVudHVyZXMgYmVsb3cgdGhlIGVxdWF0b3IuPFwvcD5cclxuXHJcbjxwPkhpcyBsaWZlLWxvbmcgYWRkaWN0aW9uIHdhcyBzb2x2aW5nIGFuZCBtYWtpbmcgcHV6emxlcywgbG9ja3MsIGFuZCBjeXBoZXJzLiBSZWNlbnRseSwgYW4gb2xkIGZhcm1lciBpbiBTb3V0aCBBbWVyaWNhLCB3aG8gd2FzIGEgaG9zdCB0byB0aGUgeW91bmcgcGh5c2ljaXN0IGluIDE5NDksIGZvdW5kIHNvbWUgcGFwZXJzIGFuZCBub3RlcyB0aGF0IGlzIGJlbGlldmVkIHRvIGhhdmUgYmVsb25nZWQgdG8gRmV5bm1hbi4gQW1vbmcgbm90ZXMgYWJvdXQgbWVzb25zIGFuZCBlbGVjdHJvbWFnbmV0aXNtLCB0aGVyZSB3YXMgYSBuYXBraW4gd2hlcmUgaGUgd3JvdGUgYSBzaW1wbGUgcHV6emxlOiAmbGRxdW87aG93IG1hbnkgZGlmZmVyZW50IHNxdWFyZXMgYXJlIHRoZXJlIGluIGEgZ3JpZCBvZiBOICZ0aW1lczsgTiBzcXVhcmVzPyZyZHF1bzsuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBzYW1lIG5hcGtpbiB0aGVyZSB3YXMgYSBkcmF3aW5nIHdoaWNoIGlzIHJlcHJvZHVjZWQgYmVsb3csIHNob3dpbmcgdGhhdCwgZm9yIE4gPSAyLCB0aGUgYW5zd2VyIGlzIDUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaG93bWFueXNxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjkzcHg7IHdpZHRoOjQzMnB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBpcyBjb21wb3NlZCBvZiBhIHNpbmdsZSBsaW5lLCBjb250YWluaW5nIG9ubHkgb25lIGludGVnZXIgTiwgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2Ygc3F1YXJlcyBpbiBlYWNoIHNpZGUgb2YgdGhlIGdyaWQgKDEgJmxlOyBOICZsZTsgMTAwKS48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgb25seSBvbmUgemVyby48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IG11c3QgYmUgcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBpbiB0aGUgaW5wdXQsIHlvdXIgcHJvZ3JhbSBtdXN0IHByaW50IGEgc2luZ2xlIGxpbmUsIGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgc3F1YXJlcyBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgaW5wdXQuPFwvcD5cclxuXHJcbjxwPlRoZSBvdXRwdXQgbXVzdCBiZSB3cml0dGVuIHRvIHN0YW5kYXJkIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d