DiviDuelo

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

요약

N이 주어질 때, 두 플레이어가 최선을 다하면 선공이 고른 약수들의 최대공약수를 1보다 크게 만들 수 있는지 판정합니다.

난이도: 보통10점 중 6점
유형: 게임 이론, 정수론, 수학
정답자: 아직 제출이 없습니다

문제

Intense Challenges Players Club (ICPC)가 DiviDuelo 대회를 개최한다.

DiviDuelo는 두 명이 번갈아 진행하는 새로운 턴제 게임이다. 이 게임에서는 수 $N$ 을 고르고 $N$ 의 약수 목록을 적는다. 예를 들어 $N = 10$ 을 고르면 1, 2, 5, 10이 적힌 목록이 된다. 두 플레이어는 차례마다 목록에서 아직 고르지 않은 약수 하나를 가져가며, 모든 약수가 선택될 때까지 이를 반복한다.

승자는 선공 플레이어가 고른 수들의 최대공약수(GCD)로 정해진다. 최대공약수가 $1$ 이 아니면 선공 플레이어가 이긴다. 최대공약수가 $1$ 이면 후공 플레이어가 이긴다.

ICPC는 대회에서 진행된 게임들의 통계를 준비하려고 한다. 두 플레이어가 최선을 다한다고 할 때, 주어진 $N$ 에 대해 선공 플레이어가 이길 수 있는지 판별하라.

입력

한 줄에 게임에서 선택된 정수 $N$ 이 주어진다 ( $1 \le N \le 10^{12}$ ).

출력

두 플레이어가 최선을 다한다고 할 때, 선공 플레이어가 이길 수 있으면 Y, 그렇지 않으면 N을 한 줄에 출력한다.

예제3

예제 1
입력
```
10
```
예상 출력
```
Y
```
예제 2
입력
```
9
```
예상 출력
```
N
```
예제 3
입력
```
1
```
예상 출력
```
N
```