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
2016-10-23 08:55:29
Do not see comments for hint . Because you can always find a better method , find your own method (Some methods in comment are more time efficient than others so you must try it yourself and then optimize it if it fails) , question is easy . Do not give up and draw diagram for more understanding. Also dont forget it Y and N not Yes and No.
2016-10-21 19:32:12
Was printing something out to debug the code and forgot to comment it out before submitting. Resulted in multiple WA. FML!
2016-08-18 15:27:59
Very Easy problem if You can observe pattern and apply brute force :) ;)
2016-07-29 08:38:53
comment helps a lot but it also destroy the pleasure of problem so please don't post the logic only post hint to that.
2016-07-27 05:08:42 sssymm
@vector1996 touche
2016-07-15 20:01:43
long - WA
long long - AC
2016-07-12 11:38:56 SANDEEP KUMAR
Solved each query in O(1) with a bit precomputation...
2016-06-30 17:30:57
Use Long in JAVA, cost me a lot of effort
2016-06-22 18:13:54
AC in one GO
1,7,19,37
A(n)th=A(n-1)th+6*(n-1)
2016-05-14 21:58:59 Luis Herrera
I used binary search but it looks that there is a simpler solution...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.