시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 70 37 32 56.140%

문제

안암골짜기에는 ALPS(Anam Lotated Pill Station) 라는 이름의 유명한 제약회사가 있다. 그곳이 유명한 이유는, 그 회사가 제조하는 모든 약은 오로지 "소주"와 "맥주" 두 가지 재료를 통해서만 만들어지기 때문이다. ALPS의 사장 재헌은 소주와 맥주를 적절히 섞음으로써 모든 병을 치료할 수 있다는 믿음 하에 약을 팔고있다.

새해를 맞이하여 약을 거하기 마신 사장 재헌은 회사에 다음과 같은 신년계획을 지시했다.

  1. 회사에서 사용하는 모든 플라스크 및 비커의 용량은 전부 1/n (n은 자연수) 꼴이여야 한다
  2. 판매 및 보관를 위한 모든 약은 플라스크 및 비커에 가득 담겨져 있어야한다
  3. 일주일에 세번 동쪽을 향해 "알프스 개객끼"를 외친다.

ALPS 회사 직원들 모두 약을 거하게 마셨기 때문에 이 지령에 대해 불만을 가지지 않고 잘 따르기로 하였다.

어느 날, 회사의 신묘한 약의 기운을 원하는 손님 홍준이 회사에 찾아와서 "정제헌"을 요구하였다. ("정제헌"은 ALPS에서 자랑하는, 잘 정제된 약이다.) ALPS의 신년계획에 의해서 모든 약은 자연수의 역수 꼴의 비커에 가득 담겨져있다. "정제헌" 또한 1/n 비커에 가득 담겨져있는 상태다. 

ALPS 사장 재헌은 홍준에게 "정제헌" 1/n 을 전부 주고싶지 않다. 때문에 그는 "정제헌" 1/n 을 각각 1/x 와 1/y 의 용량을 가진 플라스크에 나눠담아서 1/x 에 담긴 "정제헌"을 홍준에게 주고 1/y 는 회사에 남기기로 하였다. 그런데 아차! 1/x 플라스크는 판매용이고, 1/y 플라스크는 보관용이다. 신년계획에 의해 1/x 플라스크와 1/y 플라스크 모두에 "정제헌"이 가득 담겨져 있어야 한다는 뜻이다!

재헌은 1/x 플라스크와 1/y 플라스크를 고르는 도중 문득 (팔라는 약은 안팔고) 신년계획을 지키면서 "정제헌"을 두 플라스크에 나눠담는 경우의 수가 궁금해졌다. 재헌이의 궁금증을 빠르게 해결하고, 홍준이에게 "정제헌"을 무사히 팔 수 있도록 도와주자.

입력

각 줄마다 테스트 케이스가 주어진다. 

각 테스트 케이스는 한줄로 "정제헌"의 용량이 "1/n" 형태로 주어진다. 1 ≤ n ≤ 10 000. 을 만족하며, 입력으로 공백이 들어오지 않는다고 가정한다.

출력

각 케이스마다 한 줄씩 "정제헌"을 플라스크에 나눠담을 수 있는 경우의 수를 출력한다. 즉, 1/x+ 1/y = 1/n 을 만족하는 자연수 {x,y} 쌍의 가지수를 출력한다. 두 플라스크 중 하나는 판매용이기 때문에, {x,y} 와 {y,x} 는 서로 다른 경우가 아니다.

예제 입력

1/2
1/4
1/1
1/5000

예제 출력

2
3
1
32

힌트