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 {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    (new Solver()).solve(in, System.out);
  }
}

class Edge {
  public int a;
  public int b;

  public Edge(int a, int b) {
    this.a = a;
    this.b = b;
  }
}

class Solver {
  public void solve(Scanner in, PrintStream out) {
    int k = in.nextInt();
    in.nextLine();
    int max = 1;
    while(max * 2 <= k)
      max <<= 1;
    ArrayList<Edge> edges = new ArrayList<Edge>();
    int[] nodes = new int[600];
    nodes[0] = 1;
    int n = 0;
    ArrayList<Integer> p = new ArrayList<Integer>();
    p.add(0);
    while(true) {
      int sum = 0;
      for(int i = 0; i < p.size(); i++)
        sum += nodes[p.get(i)];
      if(sum == max) break;
      for(int i = n + 1; i <= n + 2; i++) {
        for(int j = 0; j < p.size(); j++) {
          nodes[i] += nodes[p.get(j)];
          edges.add(new Edge(i, p.get(j)));
        }
      }
      p.clear();
      for(int i = 0; i < 2; i++) 
        p.add(++n);
    }
    for(int i = n + 1, j = 0; j < p.size();j++, i++) {
      nodes[i] = nodes[n];
      edges.add(new Edge(i, p.get(j)));
    }
    for(int i = 0;i < p.size();i++){
      p.set(i,++n);
    }
    ++n;
    for(int i = 0; i < edges.size(); i++) {
      if(edges.get(i).a == 1)
        edges.get(i).a = n;
      if(edges.get(i).b == 1)
        edges.get(i).b = n;
    }
    for(int i = 0; i < p.size(); i++)
      if(p.get(i) == 1)
        p.set(i, n);
    nodes[n] = 1;
    nodes[1] = Integer.MAX_VALUE;
    for(int i = 0; i < p.size(); i++)
      edges.add(new Edge(1, p.get(i)));
    int cur = max / 2;
    while(cur > 0) {
      if((cur & k) == cur) {
        for(int i = 1; i <= n; i++) {
          if(cur == nodes[i]) {
            int _max = cur;
            int prev = i;
            while(_max != max) {
              edges.add(new Edge(prev, ++n));
              prev = n;
              _max <<= 1;
            }
            edges.add(new Edge(prev, 1));
            break;
          }
        }
      }
      cur >>= 1;
    }
    char[][] ans = new char[n + 1][n + 1];
    for(int i = 0;i < edges.size(); i++) {
      ans[edges.get(i).a][edges.get(i).b] = 'Y';
      ans[edges.get(i).b][edges.get(i).a] = 'Y';
    }
    out.println(n + 1);
    for(int i = 0; i <= n; i++) {
      for(int j = 0; j <= n; j++) {
        if(ans[i][j] == 'Y')
          out.print(ans[i][j]);
        else
          out.print('N');
      }
      out.println();
    }
  }
}