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 B228 {
public static void main(String[] args) throws IOException
{
    Scanner input = new Scanner(System.in);
    
    int k = input.nextInt();
    //for(int k = 999999488; k >= 0; k--)
    {
        g = new boolean[10000][10000];
        at = 2;
        //System.out.println(k);
    log = 0;
    for(int i = 0; i<30;i++)
    {
        if(((1<<i) & k) > 0)
            log = i+1;
    }
    int last = 0;
    for(int i = 0; i<2*log; i++)
    {
        g[last][at] = g[at][last] = true;
        last = at;
        at++;
    }
    g[last][1] = g[1][last] = true;
    last = 0;
    for(int i = 0; i<2*log; i++)
    {
        g[last][at] = g[at][last] = true;
        g[last][at+1] = g[at+1][last] = true;
        g[at+1][at+2] = g[at+2][at+1] = true;
        g[at][at+2] = g[at+2][at] = true;
        at += 3;
        last = at - 1;
    }
    k--;
    for(int i = 1; i<30; i++)
    {
        if(((1<<i) & k) > 0)
        {
            int from = 2 + 2 * i;
            int to = 1 + 2 * log + 3 * i;
            g[from][to] = g[to][from] = true;
        }
    }
    if(k%2 == 1)
    {
        last = 0;
        for(int i = 0; i<2*log; i++)
        {
            g[last][at] = g[at][last] = true;
            last = at;
            at++;
        }
        g[last][1] = g[1][last] = true;
    }
    PrintWriter out = new PrintWriter(System.out);
    int n = at;
    out.println(at);
    for(int i = 0; i<n; i++)
    {
        for(int j = 0; j<n; j++)
            out.print(g[i][j] ? 'Y' : 'N');
        out.println();
    }
    out.close();
    }
}
static int log;
static boolean[][] g;
static void add(int pow)
{
    int last = 2 + 2*(log - pow - 1);
    for(int i = 0; i<=pow; i++)
    {
        //System.out.println(last+" "+at);
        for(int j = 0; j<2; j++)
        {
            g[last][at+j] = g[at+j][last] = true;
            g[at+j][last+3] = g[last+3][at+j] = true;
        }
        g[last+2][last+1] = g[last+1][last+2] = true;
        at += 3;
        last = at-1;
    }
    g[last][1] = g[1][last] = true;
}
static int at;
}