BEENUMS - Beehive Numbers

A beehive is an enclosed structure in which some honey bee species live and raise their young. In this problem we consider a two-dimensional sketch of the beehives. Each beehive is composed of a certain number of cells, where each cell is a regular hexagon. Each cell may have some neighbors, which are other cells that share a side with that cell. A cell with exactly 6 neighbors is an internal cell, while a cell with fewer neighbors is an external one. Notice that an external cell can always be changed to internal by adding some neighbor cells.

We are interested in a particular class of beehives. This class of valid beehives is defined recursively as follows: a) a single cell is a valid beehive; and b) given a valid beehive B, if we add the minimum number of cells such that each external cell of B becomes an internal cell, the result is a valid beehive.

The number of cells in a valid beehive is called a beehive number. Given an integer N, you must decide whether it is a beehive number.

Input

Each test case is described using a single line. The line contains an integer N (1 ≤ N ≤ 109). The end of input is indicated with a line containing a single −1.

Output

For each test case, output a single line containing an uppercase “Y” if N is a beehive number, or an uppercase “N” otherwise.

Example

Input:
43
1
7
19
15
-1

Output:
N
Y
Y
Y
N

Added by:Pablo Ariel Heiber
Date:2010-09-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET
Resource:FCEyN UBA ICPC Selection 2010

hide comments
2017-02-18 16:46:06
Very easy
2017-02-15 16:46:33
Very easy, search for beehive number for hint!
AC in one Go!!
2017-01-18 14:33:03
I guess there is some problem with the problem statement,,but after some description in the comment section it is easy to solve..


Last edit: 2017-01-18 14:33:28
2017-01-11 16:03:38
a piece of cake :p
2017-01-07 08:27:29
one of the easiest problem :D Don't think too much !!!
2017-01-04 19:53:49
my 26th
2016-12-16 11:17:24
Most confusing problem ever i have solved!Though i solved this using binary search,but till now didn't get this what problem setter said by this " In this problem we consider a two-dimensional sketch of the beehives. Each
beehive is composed of a certain number of cells, where each cell is a regular hexagon.
Each cell may have some neighbors, which are other cells that share a side with that cell.".If anyone please explain this,i will be very thankfull to him :)
2016-12-06 22:30:34
See the sequence 1, 1 + 6, 1 + 6 + 12, ... and you will get the solution
2016-11-18 08:03:47 Simran Saha
I am having difficulty in understanding the problem. Can anybody give a better explanation?
2016-11-03 02:38:34
48th :)
Very simple, AC in one go, 0 sec.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.