문제
6, 10, 15는 제곱수가 아니다. 하지만, 세 수를 곱한 수 900은 제곱수이다.
이러한 원소의 곱이 제곱수가 되는 양의 정수로 이루어진 집합을 "흥미로운 집합"이라고 한다. {6, 10, 15}와 {25}는 흥미로운 집합이다.
또, 흥미로운 집합에서 원소의 곱을 흥미로운 집합의 값이라고 한다.
집합 S가 주어졌을 때, S의 공집합이 아닌 부분집합 중에서 가장 작은 흥미로운 집합의 값을 구하는 프로그램을 작성하시오.
출력
각 테스트 케이스에 대해서, S의 공집합이 아닌 부분집합 중 흥미로운 집합의 값이 가장 작은 집합의 값을 k2라고 했을 때, k를 출력한다. 만약, 흥미로운 집합이 없다면 none을 출력한다.
예제 출력 1
5
none
3580746020392020480
W3sicHJvYmxlbV9pZCI6IjM2NDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3NjVcdWJiZjhcdWI4NWNcdWM2YjQgXHVjOWQxXHVkNTY5IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHQ2LCAxMCwgMTVcdWIyOTQgXHVjODFjXHVhY2YxXHVjMjE4XHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWMxMzggXHVjMjE4XHViOTdjIFx1YWNmMVx1ZDU1YyBcdWMyMTggOTAwXHVjNzQwIFx1YzgxY1x1YWNmMVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0XHViN2VjXHVkNTVjIFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWFjZjFcdWM3NzQgXHVjODFjXHVhY2YxXHVjMjE4XHVhYzAwIFx1YjQxOFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWM5ZDFcdWQ1NjlcdWM3NDQgJnF1b3Q7XHVkNzY1XHViYmY4XHViODVjXHVjNmI0IFx1YzlkMVx1ZDU2OSZxdW90O1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIHs2LCAxMCwgMTV9XHVjNjQwIHsyNX1cdWIyOTQgXHVkNzY1XHViYmY4XHViODVjXHVjNmI0IFx1YzlkMVx1ZDU2OVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNjEwLCBcdWQ3NjVcdWJiZjhcdWI4NWNcdWM2YjQgXHVjOWQxXHVkNTY5XHVjNWQwXHVjMTFjIFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWFjZjFcdWM3NDQgXHVkNzY1XHViYmY4XHViODVjXHVjNmI0IFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWFjMTJcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM5ZDFcdWQ1NjkgU1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBTXHVjNzU4IFx1YWNmNVx1YzlkMVx1ZDU2OVx1Yzc3NCBcdWM1NDRcdWIyY2MgXHViZDgwXHViZDg0XHVjOWQxXHVkNTY5IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1ZDc2NVx1YmJmOFx1Yjg1Y1x1YzZiNCBcdWM5ZDFcdWQ1NjlcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAsIFx1YjQ1MCBcdWM4MTVcdWMyMTggYVx1YzY0MCBiXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuICgxICZsdDsgYSAmbHQ7IGIgJmxlOyA0OTAwKSBcdWI0NTAgXHVjMjE4XHViMjk0IFx1YzlkMVx1ZDU2OSBTXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gUyA9IHt4ICZpc2luOyBOIHwgYSAmbGU7IHggJmxlOyBifSAoTlx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMTggXHVjOWQxXHVkNTY5KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgU1x1Yzc1OCBcdWFjZjVcdWM5ZDFcdWQ1NjlcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OSBcdWM5MTEgXHVkNzY1XHViYmY4XHViODVjXHVjNmI0IFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWFjMTJcdWM3NzQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM5ZDFcdWQ1NjlcdWM3NTggXHVhYzEyXHVjNzQ0IGs8c3VwPjI8XC9zdXA+XHViNzdjXHVhY2UwIFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIGtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1ZDc2NVx1YmJmOFx1Yjg1Y1x1YzZiNCBcdWM5ZDFcdWQ1NjlcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0IG5vbmVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM2NDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIaXAgVG8gQmUgU3F1YXJlIiwiZGVzY3JpcHRpb24iOiI8cD5Ob25lIG9mIHRoZSBudW1iZXJzIDYsIDEwLCAxNSBpcyBhIHNxdWFyZSwgYnV0IHRoZWlyIHByb2R1Y3QsIHRoZSBudW1iZXIgOTAwLCBpcyBhIHNxdWFyZS4gV2UgYXJlIGludGVyZXN0ZWQgaW4gc2V0cyBvZiBwb3NpdGl2ZSBpbnRlZ2VycywgdGhlIHByb2R1Y3Qgb2Ygd2hpY2ggaXMgYSBzcXVhcmUuIFdlIGNhbGwgc3VjaCBhIHNldCBISVAgKHRoaXMgc3RhbmRzIGZvciBIYXMgSW50ZXJlc3RpbmcgUHJvZHVjdCkuIEV2aWRlbnRseSB7NiwgMTAsIDE1fSBpcyBISVAsIGFuZCBzbyBpcyB7MjV9LjxcL3A+XHJcblxyXG48cD5Nb3JlIGdlbmVyYWxseSwgZ2l2ZW4gYSBzZXQgb2YgcG9zaXRpdmUgaW50ZWdlcnMsIGRvZXMgaXQgaGF2ZSBhIG5vbi1lbXB0eSBzdWJzZXQgd2hpY2ggaXMgSElQLCBhbmQgaWYgc28sIGZvciB3aGljaCBvZiB0aGUgSElQIHN1YnNldHMgd2lsbCB0aGUgcHJvZHVjdCBiZSBtaW5pbWFsPzxcL3A+XHJcblxyXG48cD5UbyBtYWtlIHRoaW5ncyBzbGlnaHRseSBlYXNpZXIgZm9yIHlvdSwgd2UgcmVzdHJpY3Qgb3VyIGF0dGVudGlvbiB0byBpbnRlcnZhbHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMgYSBhbmQgYiBvbiBhIHNpbmdsZSBsaW5lICgxICZsdDsgYSAmbHQ7IGIgJmxlOyA0OTAwKS4gVGhlc2UgaW50ZWdlcnMgZGVzY3JpYmUgdGhlIGludGVydmFsIEEgPSB7eCAmaXNpbjsgTiB8IGEgJmxlOyB4ICZsZTsgYn08XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IHRoZSBsZWFzdCBudW1iZXIgayBzdWNoIHRoYXQgdGhlIHByb2R1Y3Qgb2YgdGhlIGVsZW1lbnRzIG9mIHNvbWUgbm9uLWVtcHR5IHN1YnNldCBYICZzdWJlOyBBIGVxdWFscyBrPHN1cD4yPFwvc3VwPi4gSWYgbm8gc3VjaCBudW1iZXIgZXhpc3RzLCBwcmludCAmbHNxdW87bm9uZSZyc3F1bzsuIFRoZSBudW1iZXIgayB3aWxsIGJlIGxlc3MgdGhhbiAyPHN1cD42MzxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==