题目描述

小可的学校要举办一场幸运抽奖活动。座位从 $1$ 号到 $n$ 号连续编号，学校公布了一个神秘的"斐波那契幸运规则"：只有座位号出现在斐波那契数列中的同学才有资格参与抽奖。

斐波那契数列的定义是：

• $F_1 = 1$
• $F_2 = 1$
• $F_i = F_{i-1} + F_{i-2}$（对于 $i \ge 3$）

于是数列的前几项为：$1, 1, 2, 3, 5, 8, 13, 21, \dots$

小可需要制作一个座位状态表，对于从 $1$ 到 $n$ 的每个座位号 $i$：

• 如果座位号 $i$ 是斐波那契数列中的数，则在表中标记为 Y（Yes，有抽奖资格）
• 如果座位号 $i$ 不是斐波那契数列中的数，则在表中标记为 N（No，没有抽奖资格）

请你帮助小可生成这个长度为 $n$ 的座位资格状态表。

输入格式

输入一个整数 $n$ $(1 \le n \le 10^4)$，表示需要检测的座位号范围从 $1$ 到 $n$。

输出格式

输出一个长度为 $n$ 的字符串，其中第 $i$ 个字符表示座位号 $i$ 的抽奖资格状态：

• Y 表示有资格
• N 表示没有资格

样例

8

YYYNYNNY

提示

样例解释

座位号 $1, 2, 3, 5, 8$ 是斐波那契数 → 标记为 Y
座位号 $4, 6, 7$ 不是斐波那契数 → 标记为 N

所以输出字符串为：YYYNYNNY

数据范围

对于所有的数据，保证 $1 \le n \le 10^4$。