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.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by Dudin Victor (duviteck@gmail.com)
 * SPbSU, Faculty of Mathematics and Mechanics
 * 2014 year
 */
public class Problem_B {

    private static char[][] table;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int k = s.nextInt();

        ArrayList<Integer> powers = new ArrayList<Integer>(32);
        int curPow = 0;
        while (k > 0) {
            if ((k & 1) == 1) {
                powers.add(curPow);
            }
            curPow++;
            k = k >> 1;
        }

        initFillGraph();

        for (int pow : powers) {
            emulateWays(pow);
        }

        System.out.println(92);
        printTable(false);
    }

    private static void emulateWays(int pow) {
        int start = 31 - pow;
        int end = 90 - 2 * pow;
        table[start][end] = table[end][start] = 'Y';
    }

    private static void initFillGraph() {
        table = new char[92][92];
        for (char[] a : table) {
            Arrays.fill(a, 'N');
        }

        // Add chain to 1
        table[0][2] = table[2][0] = 'Y';

        int prev = 2;
        int next = 3;
        while (prev < 31) {
            table[prev][next] = table[next][prev] = 'Y';
            prev++;
            next++;
        }

//        printTable(true);
//        System.out.println();
//        System.out.println();

        // Add binary chain to 2
        table[1][90] = table[90][1] = 'Y';
        table[1][91] = table[91][1] = 'Y';

        prev = 90;
        next = 88;
        while (prev > 32) {
            table[prev][next] = table[next][prev] = 'Y';
            table[prev][next + 1] = table[next + 1][prev] = 'Y';
            table[prev + 1][next] = table[next][prev + 1] = 'Y';
            table[prev + 1][next + 1] = table[next + 1][prev + 1] = 'Y';
            prev -= 2;
            next -= 2;
        }

//        printTable(true);
//        System.out.println();
//        System.out.println();
    }

    private static void printTable(boolean withNumbers) {
        StringBuilder sb = new StringBuilder(92 * (92 + 2));
        int cnt = 1;
        for (char[] a : table) {
            if (withNumbers) sb.append(String.format("%2d ", cnt));
            sb.append(a);
            sb.append("\n");
            cnt++;
        }

        System.out.println(sb.toString());
    }
}