BEENUMS - Beehive Numbers

no tags 

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

hide comments
jainnamah: 2021-07-30 19:24:01

my 50th :)

reberog19: 2021-05-10 06:26:46

Simple question just find the pattern and use roots of a quadratic equation for O(1) soln

dileep_32: 2021-04-28 06:00:59

use long long.
sample cases are correct

Last edit: 2021-04-28 06:02:04
distructo: 2020-09-18 17:34:59

While using binary search take sqrt of n for end :)

Last edit: 2020-09-18 17:35:15
trhgquan: 2020-04-03 07:10:14

meow

bohot_hard_123: 2019-12-29 05:35:04

the first line of provided input (43) is wrong;

aj_254: 2019-05-18 00:33:43

beautiful question just observe pattern .... 1,1+6,1+6+12,1+6+12+18.... next layer contain 6*lyaer number+prev

kamesh11: 2018-12-02 10:34:05

My first ever application of Binary Search :)

vvp_15: 2018-07-26 17:09:25

yo..AC in one go

kuchnahiaata: 2018-03-28 22:26:16

HINT: SEQUENCES AND SERIES :)


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