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

public class Main {
    
    static final long MOD = 1000000007;
    static void mark(boolean[][] conn, int i, int j) {
        conn[i][j] = conn[j][i] = true;
    }
    
    public static void main(String[] args) throws Exception {
        FastScanner scan = new FastScanner(System.in);
        int num = scan.nextInt();
        int n = 1000;
        boolean[][] conn = new boolean[n][n];
        int start = 0;
        int end = 1;
        int[] from = new int[11];
        int[] to = new int[11];
        from[0] = start;
        to[0] = start + 1;
        for (int i = 1; i < from.length; i++) {
            from[i] = 10 * i;
            to[i] = 10 * (i + 1);
            for (int j = from[i - 1]; j < to[i - 1]; j++) {
                for (int k = from[i]; k < to[i]; k++) {
                    mark(conn, j, k);
                }
            }
        }
        int[] dist = new int[13];
        dist[0] = end;
        for (int i = 1; i < dist.length; i++) {
            dist[i] = 900 + i;
            mark(conn, dist[i], dist[i - 1]);
        }
        int index = 300;
        int level = 0;
        while (num > 0) {
            int digit = num % 10;
            for (int i = 0; i < digit; i++) {
                for (int j = from[level]; j < to[level]; j++) {
                    mark(conn, j, index);
                }
                mark(conn, index, dist[10 - level]);
                index++;
            }
            num /= 10;
            level++;
        }
        
        System.out.println(n);
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                builder.append(conn[i][j] ? 'Y' : 'N');
            }
            builder.append('\n');
        }
        System.out.print(builder.toString());
        System.out.flush();
    }
}

class FastScanner {
    BufferedReader in;
    StringTokenizer tok;

    public FastScanner(InputStream in) {
        this.in = new BufferedReader(new InputStreamReader(in));
        tok = new StringTokenizer("");
    }

    private String tryReadNextLine() {
        try {
            return in.readLine();
        } catch (Exception e) {
            throw new InputMismatchException();
        }
    }

    public String nextToken() {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(next());
        }
        return tok.nextToken();
    }

    public String next() {
        String newLine = tryReadNextLine();
        if (newLine == null)
            throw new InputMismatchException();
        return newLine;
    }

    public int nextInt() {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() {
        return Long.parseLong(nextToken());
    }

}