시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB3001037430.833%

문제

알렉산드리아의 디오판토스는 알렉산드리아에 살던 이집트 수학자이다. 그는 정수로된 해 만을 가지는 다항 방정을 처음으로 연구한 수학자이다. 그를 기리기 위해서 후대에 이 방정식은 디오판토스 방정식이라고 이름이 붙었다. 

가장 유명한 디오판토스 방정식은 \(x^n + y^n = z^n\)이다. 페르마는 \(n\) > 2인 경우에 정수해가 존재하지 않는다고 추론했고, 앤드루 와일스가 증명했다. 

다음과 같은 디오판토스 방정식이 있다.

\(\frac{1}{x} + \frac{1}{y} = \frac{1}{n}\) where \(x,y,n \in \mathbb{N}^+\)

\(n\)이 주어졌을 때, 이 방정식의 해는 총 몇 개일까? (\(x\) ≤ \(y\)) \(n\) = 4인 경우에 아래와 같이 총 3가지 해가 존재한다.

\(\frac{1}{5} + \frac{1}{20} = \frac{1}{4}\) \(\frac{1}{6} + \frac{1}{12} = \frac{1}{4}\) \(\frac{1}{8} + \frac{1}{8} = \frac{1}{4}\)

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, \(n\)이 주어진다. (1 ≤ \(n\) ≤ 109)

출력

각각의 테스트 케이스마다 "Scenario #i:"를 출력하고, 주어진 n에 대한 방정식의 해의 개수를 출력한다. 각 테스트 케이스 사이에는 빈 줄을 출력한다.

예제 입력 1

2
4
1260

예제 출력 1

Scenario #1:
3

Scenario #2:
113
W3sicHJvYmxlbV9pZCI6Ijc1MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NGNcdWI4MDlcdWMwYjBcdWI0ZGNcdWI5YWNcdWM1NDRcdWM3NTggXHViNTE0XHVjNjI0XHVkMzEwXHVkMWEwXHVjMmE0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NGNcdWI4MDlcdWMwYjBcdWI0ZGNcdWI5YWNcdWM1NDRcdWM3NTggXHViNTE0XHVjNjI0XHVkMzEwXHVkMWEwXHVjMmE0XHViMjk0IFx1YzU0Y1x1YjgwOVx1YzBiMFx1YjRkY1x1YjlhY1x1YzU0NFx1YzVkMCBcdWMwYjRcdWIzNTggXHVjNzc0XHVjOWQxXHVkMmI4IFx1YzIxOFx1ZDU1OVx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yjg1Y1x1YjQxYyBcdWQ1NzQgXHViOWNjXHVjNzQ0IFx1YWMwMFx1YzljMFx1YjI5NCBcdWIyZTRcdWQ1NmQgXHViYzI5XHVjODE1XHVjNzQ0IFx1Y2M5OFx1Yzc0Y1x1YzczY1x1Yjg1YyBcdWM1ZjBcdWFkNmNcdWQ1NWMgXHVjMjE4XHVkNTU5XHVjNzkwXHVjNzc0XHViMmU0LiBcdWFkZjhcdWI5N2MgXHVhZTMwXHViOWFjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQ2YzRcdWIzMDBcdWM1ZDAgXHVjNzc0IFx1YmMyOVx1YzgxNVx1YzJkZFx1Yzc0MCBcdWI1MTRcdWM2MjRcdWQzMTBcdWQxYTBcdWMyYTQgXHViYzI5XHVjODE1XHVjMmRkXHVjNzc0XHViNzdjXHVhY2UwIFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWJkOTlcdWM1YzhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWM3MjBcdWJhODVcdWQ1NWMgXHViNTE0XHVjNjI0XHVkMzEwXHVkMWEwXHVjMmE0IFx1YmMyOVx1YzgxNVx1YzJkZFx1Yzc0MCBcXCh4Xm4gKyB5Xm4gPSB6Xm5cXClcdWM3NzRcdWIyZTQuIFx1ZDM5OFx1Yjk3NFx1YjljOFx1YjI5NCBcXChuXFwpICZndDsgMlx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjODE1XHVjMjE4XHVkNTc0XHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWFjZTAgXHVjZDk0XHViODYwXHVkNTg4XHVhY2UwLCBcdWM1NjRcdWI0ZGNcdWI4ZTggXHVjNjQwXHVjNzdjXHVjMmE0XHVhYzAwIFx1Yzk5ZFx1YmE4NVx1ZDU4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWI1MTRcdWM2MjRcdWQzMTBcdWQxYTBcdWMyYTQgXHViYzI5XHVjODE1XHVjMmRkXHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFwoXFxmcmFjezF9e3h9ICsgXFxmcmFjezF9e3l9ID0gXFxmcmFjezF9e259XFwpIHdoZXJlIFxcKHgseSxuIFxcaW4gXFxtYXRoYmJ7Tn1eK1xcKTxcL3A+XHJcblxyXG48cD5cXChuXFwpXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWJjMjlcdWM4MTVcdWMyZGRcdWM3NTggXHVkNTc0XHViMjk0IFx1Y2QxZCBcdWJhODcgXHVhYzFjXHVjNzdjXHVhZTRjPyAoXFwoeFxcKSAmbGU7IFxcKHlcXCkpIFxcKG5cXCkgPSA0XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1Y2QxZCAzXHVhYzAwXHVjOWMwIFx1ZDU3NFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxcKFxcZnJhY3sxfXs1fSArIFxcZnJhY3sxfXsyMH0gPSBcXGZyYWN7MX17NH1cXCkgXFwoXFxmcmFjezF9ezZ9ICsgXFxmcmFjezF9ezEyfSA9IFxcZnJhY3sxfXs0fVxcKSBcXChcXGZyYWN7MX17OH0gKyBcXGZyYWN7MX17OH0gPSBcXGZyYWN7MX17NH1cXCk8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFxcKG5cXClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFxcKG5cXCkgJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgJnF1b3Q7U2NlbmFyaW8gI2k6JnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVjOGZjXHVjNWI0XHVjOWM0IG5cdWM1ZDAgXHViMzAwXHVkNTVjIFx1YmMyOVx1YzgxNVx1YzJkZFx1Yzc1OCBcdWQ1NzRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijc1MTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEaW9waGFudHVzIG9mIEFsZXhhbmRyaWEiLCJkZXNjcmlwdGlvbiI6IjxwPkRpb3BoYW50dXMgb2YgQWxleGFuZHJpYSB3YXMgYW4gZWd5cHQgbWF0aGVtYXRpY2lhbiBsaXZpbmcgaW4gQWxleGFuZHJpYS4gSGUgd2FzIG9uZSBvZiB0aGUgXHVmYjAxcnN0IG1hdGhlbWF0aWNpYW5zICZuYnNwO3RvIHN0dWR5IGVxdWF0aW9ucyB3aGVyZSB2YXJpYWJsZXMgd2VyZSByZXN0cmljdGVkIHRvIGludGVncmFsIHZhbHVlcy4gSW4gaG9ub3Igb2YgaGltLCB0aGVzZSBlcXVhdGlvbnMgYXJlIGNvbW1vbmx5IGNhbGxlZCBkaW9waGFudGluZSBlcXVhdGlvbnMuIE9uZSBvZiB0aGUgbW9zdCBmYW1vdXMgZGlvcGhhbnRpbmUgZXF1YXRpb24gaXNcXCh4Xm4gKyB5Xm4gPSB6Xm5cXCkuIEZlcm1hdCBzdWdnZXN0ZWQgdGhhdCBmb3IgXFwoblxcKSAmZ3Q7IDIsIHRoZXJlIGFyZSBubyBzb2x1dGlvbnMgd2l0aCBwb3NpdGl2ZSBpbnRlZ3JhbCB2YWx1ZXMgZm9yIFxcKHhcXCksIFxcKHlcXCkgYW5kIFxcKHpcXCkuIEEgcHJvb2Ygb2YgdGhpcyB0aGVvcmVtIChjYWxsZWQgRmVybWF0JnJzcXVvO3MgbGFzdCB0aGVvcmVtKSB3YXMgZm91bmQgb25seSByZWNlbnRseSBieSBBbmRyZXcgV2lsZXMuPFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyIHRoZSBmb2xsb3dpbmcgZGlvcGhhbnRpbmUgZXF1YXRpb246PFwvcD5cclxuXHJcbjxwPlxcKFxcZnJhY3sxfXt4fSArIFxcZnJhY3sxfXt5fSA9IFxcZnJhY3sxfXtufVxcKSB3aGVyZSBcXCh4LHksbiBcXGluIFxcbWF0aGJie059XitcXCkgKDEpPFwvcD5cclxuXHJcbjxwPkRpb3BoYW50dXMgaXMgaW50ZXJlc3RlZCBpbiB0aGUgZm9sbG93aW5nIHF1ZXN0aW9uOiBmb3IgYSBnaXZlbiBuLCBob3cgbWFueSBkaXN0aW5jdCBzb2x1dGlvbnMgKGkuIGUuLCBzb2x1dGlvbnMgc2F0aXNmeWluZyBcXCh4XFwpICZsZTsgXFwoeVxcKSkgZG9lcyBlcXVhdGlvbiAoMSkgaGF2ZT8gRm9yIGV4YW1wbGUsIGZvciBcXChuXFwpID0gNCwgdGhlcmUgYXJlIGV4YWN0bHkgdGhyZWUgZGlzdGluY3Qgc29sdXRpb25zOjxcL3A+XHJcblxyXG48cD5cXChcXGZyYWN7MX17NX0gKyBcXGZyYWN7MX17MjB9ID0gXFxmcmFjezF9ezR9XFwpIFxcKFxcZnJhY3sxfXs2fSArIFxcZnJhY3sxfXsxMn0gPSBcXGZyYWN7MX17NH1cXCkgXFwoXFxmcmFjezF9ezh9ICsgXFxmcmFjezF9ezh9ID0gXFxmcmFjezF9ezR9XFwpPFwvcD5cclxuXHJcbjxwPkNsZWFybHksIGVudW1lcmF0aW5nIHRoZXNlIHNvbHV0aW9ucyBjYW4gYmVjb21lIHRlZGlvdXMgZm9yIGJpZ2dlciB2YWx1ZXMgb2YgXFwoblxcKS4gQ2FuIHlvdSBoZWxwIERpb3BoYW50dXMgY29tcHV0ZSB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IHNvbHV0aW9ucyBmb3IgYmlnIHZhbHVlcyBvZiBuIHF1aWNrbHk/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiBzY2VuYXJpb3MuIEVhY2ggc2NlbmFyaW8gY29uc2lzdHMgb2Ygb25lIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBudW1iZXIgXFwoblxcKSAoMSAmbGU7IFxcKG5cXCkgJmxlOyAxMDxzdXA+OTxcL3N1cD4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgZm9yIGV2ZXJ5IHNjZW5hcmlvIGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nICZsZHF1bztTY2VuYXJpbyAjaTomcmRxdW87LCB3aGVyZSBpIGlzIHRoZSBudW1iZXIgb2YgdGhlIHNjZW5hcmlvIHN0YXJ0aW5nIGF0IDEuIE5leHQsIHByaW50IGEgc2luZ2xlIGxpbmUgd2l0aCB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IHNvbHV0aW9ucyBvZiBlcXVhdGlvbiAoMSkgZm9yIHRoZSBnaXZlbiB2YWx1ZSBvZiBcXChuXFwpLiBUZXJtaW5hdGUgZWFjaCBzY2VuYXJpbyB3aXRoIGEgYmxhbmsgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

University > Tu-Darmstadt Programming Contest > TUD Contest 2006 1번