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.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Random;
import java.util.TreeSet;

public class D {
    
    static long pow(int i) {
        long ret=1;
        for (int j=0; j<i; j++) {
            ret*=i;
        }
        
        return (int)Math.sqrt(ret);
    }
    
    static char[][] compute(int k) {
        
        int total=0;
        int vcnt=-1;
        
        HashSet<Long> edges=new HashSet<Long>();
        
        if(k==1) {
            vcnt=2;
            total=1;
            
            edges.add(1L);
        } else if(k==2) {
            vcnt=4;
            total=2;
            
            edges.add(2L);
            edges.add(3L);
            
            edges.add((2L<<32)+1L);
            edges.add((3L<<32)+1L);
        } else {
            int n=-1;
            for (int i=1; i<Math.sqrt(998); i++) {
                if(pow(i)>k) {
                    n=i+1;
                    break;
                }
            }
            
            vcnt=n*n+2;
            
            long[] cnt=new long[n], cntn=new long[n];
            for (int i=0; i<n; i++) {
                int v1=i+2;
                
                long e=(long)v1;
                edges.add(e);
                cnt[i]=1;
            }
            
            for (int layer=1; layer<n; layer++) {
                total=0;
                Arrays.fill(cntn, 0);
                for (int i=0; i<n; i++) {
                    int v2=layer*n+i+2;
                    
                    for (int j=layer<n-1? i: 0; j<n; j++) {
                        if(layer<n-1||total+cnt[j]<=k) {
                            int v1=(layer-1)*n+j+2;
                            cntn[i]+=cnt[j];
                            total+=cnt[j];
                            
                            long e=((long)v1<<32)+(long)v2;
                            edges.add(e);
                            
                            if(layer==n-1) {
                                e=((long)v2<<32)+1L;
                                edges.add(e);
                            }
                        }
                    }
                }
                long[] tmp=cnt; cnt=cntn; cntn=tmp;
            }
            
            for (int i=0; i<(k-total); i++) {
                int v1=0;
                for (int j=0; j<n; j++) {
                    int v2=vcnt+i*n+j;
                    long e=((long)v1<<32)+(long)v2;
                    edges.add(e);
                    
                    v1=v2;
                }
                long e=((long)v1<<32)+1L;
                edges.add(e);
            }
            
            vcnt+=(k-total)*n;
        }
        

        char[][] out=new char[vcnt][vcnt];
        for (int i=0; i<out.length; i++) {
            Arrays.fill(out[i], 'N');
        }
        
        for (long e: edges) {
            int v1=(int)(e>>32);
            int v2=(int)e;
            
            out[v1][v2]='Y';
            out[v2][v1]='Y';
        }
        
        return out;
    }
    
    
    
    
    
    
    
    
    static void run_stream(InputStream ins) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int k=Integer.parseInt(br.readLine());
        run(k);
    }

    static Random r=new Random();
    static void run_random() throws IOException {
        run(r.nextInt(1000000000)+1000000000);
    }

    private static void run(int k) {
        char[][] ret=compute(k);
        
        System.out.println(ret.length);
        for (int i=0; i<ret.length; i++) {
            for (int j=0; j<ret.length; j++) {
                System.out.print(ret[i][j]);
            }
            System.out.println();
        }
        
//        int[] cnt=new int[ret.length];
//        cnt_path(ret, cnt);
//        
//        System.out.println("path cnt: "+cnt[1]);
//        System.out.println("diff: "+(k-cnt[1]));
    }
    

    public static void main(String[] args) throws IOException {
        run_stream(System.in);
        //run_random();
    }
    
    
    static void cnt_path(char[][] adj, int[] out) {
        int n=out.length;
        final int[] dist=new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        TreeSet<Integer> t=new TreeSet<Integer>(new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                int ret=dist[o1]-dist[o2];
                if(ret==0) {
                    ret=o1-o2;
                }
                return ret;
            }});
        
        dist[0]=0; out[0]=1;
        t.add(0);
        
        while(!t.isEmpty()) {
            int i=t.first();
            t.remove(i);
            
            for (int j=0; j<n; j++) {
                if(adj[i][j]=='Y') {
                    if(dist[j]>dist[i]+1) {
                        t.remove(j);
                        dist[j]=dist[i]+1;
                        out[j]=out[i];
                        t.add(j);
                    } else if(dist[j]==dist[i]+1) {
                        out[j]+=out[i];
                    }
                }
            }
        }
    }
}