Problem: Fox Ciel wants to write a task for a programming contest. The task is: "You are given a simple undirected graph with n vertexes. Each its edge has unit length. You should calculate the number of shortest paths between vertex 1 and vertex 2."

Same with some writers, she wants to make an example with some certain output: for example, her birthday or the number of her boyfriend. Can you help her to make a test case with answer equal exactly to k?

Input

The first line contains a single integer k (1 ≤ k ≤ 109).

Output

You should output a graph G with n vertexes (2 ≤ n ≤ 1000). There must be exactly k shortest paths between vertex 1 and vertex 2 of the graph.

The first line must contain an integer n. Then adjacency matrix G with n rows and n columns must follow. Each element of the matrix must be 'N' or 'Y'. If Gij is 'Y', then graph G has a edge connecting vertex i and vertex j. Consider the graph vertexes are numbered from 1 to n.

The graph must be undirected and simple: Gii = 'N' and Gij = Gji must hold. And there must be at least one path between vertex 1 and vertex 2. It's guaranteed that the answer exists. If there multiple correct answers, you can output any of them. 

Examples

Input

2

Output

4
NNYY
NNYY
YYNN
YYNN

Input

9

Output

8
NNYYYNNN
NNNNNYYY
YNNNNYYY
YNNNNYYY
YNNNNYYY
NYYYYNNN
NYYYYNNN
NYYYYNNN

Input

1

Output

2
NY
YN

Note

In first example, there are 2 shortest paths: 1-3-2 and 1-4-2.

In second example, there are 9 shortest paths: 1-3-6-2, 1-3-7-2, 1-3-8-2, 1-4-6-2, 1-4-7-2, 1-4-8-2, 1-5-6-2, 1-5-7-2, 1-5-8-2.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;


public class B {

    static StringTokenizer st;
    static BufferedReader br;
    static PrintWriter pw;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int k = nextInt();
        int cur = 3;
        int n = 1000;
        char[][]a = new char[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(a[i], 'N');
        }
        int last = -1, leng = 0;
        for (int i = 0; i < 30; i++) {
            if ((k & (1 << i)) != 0) {
                if (i==0) {
                    cur++;
                    add(1, cur, a);
                    last = cur;
                    leng = 1;
                }
                else {
                    if (last != -1) {
                        while (leng != i) {
                            add(cur, cur+1, a);
                            cur++;
                            leng++;
                        }
                        last = cur;
                    }
                    add(1, cur+1, a);
                    add(1, cur+2, a);
                    cur += 2;
                    for (int j = 1; j < i; j++) {
                        add(cur-1, cur+1, a);
                        add(cur-1, cur+2, a);
                        add(cur, cur+1, a);
                        add(cur, cur+2, a);
                        cur += 2;
                    }
                    add(cur-1, cur+1, a);
                    add(cur, cur+1, a);
                    cur++;
                    if (last != -1) {
                        add(last, cur, a);
                    }
                    leng = i+1;
                    last = cur;
                }
            }
        }
        add(2, cur, a);
        pw.println(cur+3);
        for (int i = 1; i <= cur+3; i++) {
            for (int j = 1; j <= cur+3; j++) {
                pw.print(a[i][j]);
            }
            pw.println();
        }
        pw.close();
    }
    private static void add(int v1, int v2, char[][] a) {
        a[v1][v2] = a[v2][v1] = 'Y';
    }
    private static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    private static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    private static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
    private static String next() throws IOException {
        while (st==null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
}