피타! 피타! 피타츄!

시간 제한1초메모리 제한1024 MB

요약

한 변의 길이가 sqrt(n)인 직각삼각형 중 정수 길이인 변이 두 개 이상인 것의 개수를 구합니다. 무한히 많으면 -1을 출력합니다.

난이도: 보통10점 중 5점
유형: 정수론, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

포켓몬스터를 좋아하는 종우는 이 게임이 상당히 수학적이고 코딩과 밀접하게 연결되어 있다는 것을 알게 되었다. 모든 이동은 유클리드 공간에서 평행하게 이루어지고, 데미지나 급소 공격 같은 계산도 상당히 복잡하다. 시리즈 이름에도 수학이 숨어 있다. 처음 발매된 레드, 그린, 블루는 RGB에서 따왔고, 블랙과 화이트는 흑백을 뜻하며, X와 Y는 미지수의 변수 이름이다. 아예 알고리즘 이름을 딴 DP 시리즈도 있다!

종우는 포켓몬들에게도 이런 요소가 숨어 있으리라 생각하고, 피카츄도 사실 피타츄에서 유래했다는 가설을 세웠다. 피카츄를 자세히 살펴보던 종우는 초기 피카츄의 꼬리에 직각이 많다는 것을 알아냈다! 피타고라스의 정리를 생각하던 종우는 문득 다음 의문이 들었다.

적어도 한 변의 길이가 $\sqrt{n}$ 인 서로 다른 모양의 직각삼각형 중에서, 적어도 두 변의 길이가 정수인 직각삼각형은 몇 개일까? 합동이 아닌 삼각형을 서로 다른 모양의 삼각형이라고 한다.

종우를 도와 문제를 풀어보자.

입력

직각삼각형이 포함해야 하는 변의 길이의 제곱을 나타내는 정수 $n(1\le n\le10^{12})$ 이 주어진다.

출력

조건을 만족하는 직각삼각형의 개수를 출력한다. 그러한 삼각형이 무한히 존재한다면 -1을 출력한다.

힌트

실제로 피카츄가 피타츄에서 유래되었다는 것은 근거가 없다.

예제5

예제 1
입력
```
6
```
예상 출력
```
0
```
예제 2
입력
```
5
```
예상 출력
```
2
```
예제 3
입력
```
1
```
예상 출력
```
-1
```
예제 4
입력
```
1000
```
예상 출력
```
6
```
예제 5
입력
```
999999999999
```
예상 출력
```
128
```