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:
//package codeforces;

import java.io.PrintWriter;
import java.util.Scanner;


public class FoxandMinimalpath {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        int k = in.nextInt();
        
        if (k == 1) {
            out.println(2);
            out.println("NY\nYN");            
        }
        else if (k == 2) {
            out.println(4);
            out.println("NNYY\nNNYY");
            out.println("YYNN\nYYNN");
        }        
        else {
            int n = 32 - Integer.numberOfLeadingZeros(k); //println(n); // number of layers        
            int N = (n + 2)*(n + 1)/2 + 1; //println(N); // number of nodes required
            boolean[][] G = new boolean[N+1][N+1];

            connect(G, 1, 3);
            connect(G, 1, 4);
            
            int start = 3;
            int end = 4;
            for (int i = 2; i <= n; i++) {
                int prev_start = start;
                
                start = end + 1;
                end = start + i;
                createLayer(G, i, start, end, prev_start);
            }
            
            connect2(G, start + 1, k);
            
            printGraph(G, N, out);
        }
        
        out.flush();        
    }
    
    private static void connect2(boolean[][] G, int start, int k) {
        int mask = 1;
        
        for (int i = 0; i < 32; i++, mask = mask << 1) {
            if ((k & mask) > 0)
                connect(G, 2, start + i);
            
        }
    }
    
    private static void printGraph(boolean[][] G, int nodes, PrintWriter out) {
        out.println(nodes);
        
        for (int i = 1; i <= nodes; i++) {
            for (int j = 1; j <= nodes; j++)
                out.print(G[i][j] ? 'Y':'N');
            
            out.println();
        }
    }
    
    private static void createLayer(boolean[][] G, int i, 
            int start, int end, 
            int prev_start) {
        
        connect(G, prev_start, start);
        
        for (int j = 1; start + j <= end; j++) {
            connect(G, start + j, prev_start, prev_start + j - 1);
        }
    }
    
    private static void connect(boolean[][] G, int i, int start, int end) {
        for (int j = start; j <= end; j++)
            connect(G, i, j);
    }
    
    private static void connect(boolean[][] G, int i, int j) {
        G[i][j] = true;
        G[j][i] = true;
    }
    
    private static void printArray(int[] a) { for (int i: a) println(i); }    
    private static void println(Object o) { System.out.println(o);}

    
}