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.util.*;
import java.io.*;

public class First2 {
    public static void main(String[] args) throws IOException {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int k = Integer.parseInt(rd.readLine());
        int[][] g = construct(k);
        pw.println(g.length);
        for(int i=0; i<g.length; i++){
            for(int j=0; j<g.length; j++){
                pw.print(g[i][j]==1 ? 'Y' : 'N');
            }
            pw.println();
        }
        pw.flush();
        pw.close();
    }
    
    
    
    static int[][] construct(int k){
        if(k==1){
            int[][] g = new int[2][2];
            g[0][1] = 1;
            g[1][0] = 1;
            return g;
        }
        if(k==2){
            int[][] g = new int[4][4];
            addEdge(g, 0, 2);
            addEdge(g, 0, 3);
            addEdge(g, 3, 1);
            addEdge(g, 2, 1);
            return g;
        }
        if(k==3){
            int[][] g = new int[5][5];
            addEdge(g, 0, 2);
            addEdge(g, 0, 3);
            addEdge(g, 0, 4);
            addEdge(g, 2, 1);
            addEdge(g, 3, 1);
            addEdge(g, 4, 1);
            return g;
        }
        if(k%2==0){
            int[][] h = construct(k/2);
            int len = h.length;
            int[][] g = new int[len+3][len+3];
            for(int x=0; x<len; x++){
                g[x][len] = h[x][1];
                g[len][x] = g[x][len];
            }
            for(int x=0; x<len; x++){
                for(int y=0; y<len; y++){
                    if(x==1 || y==1) continue;
                    g[x][y] = h[x][y];
                }
            }
            addEdge(g, len, len+1);
            addEdge(g, len, len+2);
            addEdge(g, len+1, 1);
            addEdge(g, len+2, 1);
            return g;
        }
        int[][] h = construct(k/2);
        int len = h.length;
        int way = L(k);
        int[][] g = new int[len+3+way-1][len+3+way-1];
        for(int x=0; x<len; x++){
            g[x][len] = h[x][1];
            g[len][x] = g[x][len];
        }
        for(int x=0; x<len; x++){
            for(int y=0; y<len; y++){
                if(x==1 || y==1) continue;
                g[x][y] = h[x][y];
            }
        }
        addEdge(g, len, len+1);
        addEdge(g, len, len+2);
        addEdge(g, len+1, 1);
        addEdge(g, len+2, 1);
        for(int i=len+3; i<g.length-1; i++){
            addEdge(g, i, i+1);
        }
        addEdge(g, g.length-1, 1);
        addEdge(g, 0, len+3);
        return g;
    }
    
    
    
    static void addEdge(int[][] a, int x, int y){
        a[x][y] = 1;
        a[y][x] = 1;
    }
    
    
    static int F(int k){
        if(f.containsKey(k)) return f.get(k);
        if(k==1) return 2;
        if(k==2) return 4;
        if(k==3) return 5;
        int ans = (k%2==0 ? F(k/2) + 3 : F(k/2) + L(k/2) + 3);
        f.put(k, ans);
        return ans;
    }
    
    static int L(int k){
        if(L.containsKey(k)) return L.get(k);
        if(k==1) return 1;
        if(k==2) return 2;
        if(k==3) return 2;
        int ans = L(k/2) + 2;
        L.put(k, ans);
        return ans;
    }
    
    static HashMap<Integer, Integer> f = new HashMap<Integer, Integer>(), L = new HashMap<Integer, Integer>();
    
    
}