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
2015-01-19 10:40:52 Rajat (1307086)
Series whose common difference is an A.P :)
2015-01-06 20:26:56 Malinga
100th !!
2014-12-10 17:04:00 #include
easy one once the series is discovered. my 49th. 2sec time limit seems too much for this problem


Last edit: 2014-12-10 17:05:11
2014-11-01 23:14:34 Aditya Paliwal
100 :D
Gonna keep the streak going :)
2014-09-20 10:43:28 Ankit Sultana
The input probably contains N > 10^9.. watch out if you are getting WA and your algo seems correct
2014-05-23 15:11:59 dinkar
guys, isn't it some what like http://www.spoj.com/problems/CANTON/ ??
2014-05-20 09:06:48 pvkcse
thanks for the test cases...178 bytes of code in python got AC in the first go...!!!
2014-02-15 07:59:09 mayank
I think problem statement is a bit unclear! It should tell that a Beehive Number implies a complete beehive, ie no cells are missing! Beehives can also be created with missing cells!
2013-11-01 05:43:23 rajul
brute force works -_- no need to think more than 2 minutes !!
2013-08-08 21:25:39 ROHIT KUMAR
"AC" in 1 go :)
plz remove the hints given in the comments...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.