DiviDuelo

Time limit1sMemory limit1024 MB

Summary

Given N up to 10^12, decide whether the first player can force the gcd of their picked divisors to be greater than 1 under optimal play.

Level: Medium6 of 10
Topics: Game theory, Number theory, Math
Solved: No attempts yet

Problem

The Intense Challenges Players Club (ICPC) is hosting a DiviDuelo tournament.

DiviDuelo is a new two-player, turn-based game. In DiviDuelo, a number $N$ is selected and the list of its divisors is written. For example, if $N = 10$ is selected, the list 1, 2, 5, 10 is written. Players alternate turns, each picking one still unpicked divisor from the list, until all divisors have been picked.

The winner is determined by the greatest common divisor (GCD) of the numbers picked by the starting player. If the GCD is not equal to $1$ , the starting player wins. If the GCD is equal to $1$ , the other player wins.

The ICPC needs statistics about the games played in the tournament. Given $N$ , determine whether the starting player can win when both players play optimally.

Input

The input is a single line containing an integer $N$ ( $1 \le N \le 10^{12}$ ), the number selected for the game.

Output

Output a single line with the letter Y if the starting player can win, and the letter N otherwise, assuming both players play optimally.

Examples3

Example 1
Input
```
10
```
Expected output
```
Y
```
Example 2
Input
```
9
```
Expected output
```
N
```
Example 3
Input
```
1
```
Expected output
```
N
```