#include <bits/stdc++.h>
using namespace std;
void PR(int x) { printf("%d\n", x); }
int mat[2010][2010];
vector<int> lvl[35];
int tmp[2010];
int main() {
  int i, j, k, n, m, rem, dim, f;
  while (scanf("%d", &rem) == 1) {
    memset(mat, 0, sizeof(mat));
    n = 2;
    f = 0;
    for (i = 29; i >= 1; i--) {
      if (rem & (1 << i)) {
        if (f == 0) {
          f = 1;
          dim = i;
          for (j = 1; j <= dim; j++) {
            (lvl[j].clear());
            lvl[j].push_back(++n);
          }
          for (j = 1; j <= dim - 1; j++) {
            mat[lvl[j][0]][lvl[j + 1][0]] = mat[lvl[j + 1][0]][lvl[j][0]] = 1;
          }
          lvl[1].push_back(++n);
          for (j = 1; j <= i; j++) {
            if (j != dim) lvl[j + 1].push_back(++n);
            if (j == 1) {
              mat[1][lvl[j][0]] = mat[lvl[j][0]][1] = 1;
              mat[1][lvl[j][1]] = mat[lvl[j][1]][1] = 1;
            } else {
              mat[lvl[j - 1][0]][lvl[j][0]] = mat[lvl[j][0]][lvl[j - 1][0]] = 1;
              mat[lvl[j - 1][0]][lvl[j][1]] = mat[lvl[j][1]][lvl[j - 1][0]] = 1;
              mat[lvl[j - 1][1]][lvl[j][0]] = mat[lvl[j][0]][lvl[j - 1][1]] = 1;
              mat[lvl[j - 1][1]][lvl[j][1]] = mat[lvl[j][1]][lvl[j - 1][1]] = 1;
            }
            if (j != dim)
              mat[lvl[j][0]][lvl[j + 1][0]] = mat[lvl[j + 1][0]][lvl[j][0]] = 1;
            if (j != dim)
              mat[lvl[j][1]][lvl[j + 1][0]] = mat[lvl[j + 1][0]][lvl[j][1]] = 1;
          }
          mat[lvl[dim][0]][2] = mat[2][lvl[dim][0]] = 1;
          if (i == dim) mat[lvl[dim][1]][2] = mat[2][lvl[dim][1]] = 1;
        } else {
          for (j = 1; j <= i; j++)
            ;
          k = 0;
          for (; j <= dim; j++) {
            tmp[++k] = ++n;
            if (k != 1) mat[tmp[k]][tmp[k - 1]] = mat[tmp[k - 1]][tmp[k]] = 1;
          }
          mat[tmp[k]][2] = mat[2][tmp[k]] = 1;
          mat[tmp[1]][lvl[i][0]] = mat[lvl[i][0]][tmp[1]] = 1;
          mat[tmp[1]][lvl[i][1]] = mat[lvl[i][1]][tmp[1]] = 1;
        }
      }
    }
    if (f == 0) dim = 1;
    if (rem & (1 << 0) == 1) {
      for (j = 1; j <= dim; j++) {
        (lvl[j].clear());
        lvl[j].push_back(++n);
      }
      for (j = 1; j <= dim - 1; j++) {
        mat[lvl[j][0]][lvl[j + 1][0]] = 1;
        mat[lvl[j + 1][0]][lvl[j][0]] = 1;
      }
      mat[1][lvl[1][0]] = mat[lvl[1][0]][1] = 1;
      mat[2][lvl[dim][0]] = mat[lvl[dim][0]][2] = 1;
    }
    PR(n);
    for ((i) = 1; (i) <= (int)(n); (i)++) {
      for ((j) = 1; (j) <= (int)(n); (j)++) {
        if (mat[i][j])
          printf("Y");
        else
          printf("N");
      }
      puts("");
    }
  }
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void PR(int x) { printf("%d\n", x); }
int mat[2010][2010];
vector<int> lvl[35];
int tmp[2010];
int main() {
  int i, j, k, n, m, rem, dim, f;
  while (scanf("%d", &rem) == 1) {
    memset(mat, 0, sizeof(mat));
    n = 2;
    f = 0;
    for (i = 29; i >= 1; i--) {
      if (rem & (1 << i)) {
        if (f == 0) {
          f = 1;
          dim = i;
          for (j = 1; j <= dim; j++) {
            (lvl[j].clear());
            lvl[j].push_back(++n);
          }
          for (j = 1; j <= dim - 1; j++) {
            mat[lvl[j][0]][lvl[j + 1][0]] = mat[lvl[j + 1][0]][lvl[j][0]] = 1;
          }
          lvl[1].push_back(++n);
          for (j = 1; j <= i; j++) {
            if (j != dim) lvl[j + 1].push_back(++n);
            if (j == 1) {
              mat[1][lvl[j][0]] = mat[lvl[j][0]][1] = 1;
              mat[1][lvl[j][1]] = mat[lvl[j][1]][1] = 1;
            } else {
              mat[lvl[j - 1][0]][lvl[j][0]] = mat[lvl[j][0]][lvl[j - 1][0]] = 1;
              mat[lvl[j - 1][0]][lvl[j][1]] = mat[lvl[j][1]][lvl[j - 1][0]] = 1;
              mat[lvl[j - 1][1]][lvl[j][0]] = mat[lvl[j][0]][lvl[j - 1][1]] = 1;
              mat[lvl[j - 1][1]][lvl[j][1]] = mat[lvl[j][1]][lvl[j - 1][1]] = 1;
            }
            if (j != dim)
              mat[lvl[j][0]][lvl[j + 1][0]] = mat[lvl[j + 1][0]][lvl[j][0]] = 1;
            if (j != dim)
              mat[lvl[j][1]][lvl[j + 1][0]] = mat[lvl[j + 1][0]][lvl[j][1]] = 1;
          }
          mat[lvl[dim][0]][2] = mat[2][lvl[dim][0]] = 1;
          if (i == dim) mat[lvl[dim][1]][2] = mat[2][lvl[dim][1]] = 1;
        } else {
          for (j = 1; j <= i; j++)
            ;
          k = 0;
          for (; j <= dim; j++) {
            tmp[++k] = ++n;
            if (k != 1) mat[tmp[k]][tmp[k - 1]] = mat[tmp[k - 1]][tmp[k]] = 1;
          }
          mat[tmp[k]][2] = mat[2][tmp[k]] = 1;
          mat[tmp[1]][lvl[i][0]] = mat[lvl[i][0]][tmp[1]] = 1;
          mat[tmp[1]][lvl[i][1]] = mat[lvl[i][1]][tmp[1]] = 1;
        }
      }
    }
    if (f == 0) dim = 1;
    if (rem & (1 << 0) == 1) {
      for (j = 1; j <= dim; j++) {
        (lvl[j].clear());
        lvl[j].push_back(++n);
      }
      for (j = 1; j <= dim - 1; j++) {
        mat[lvl[j][0]][lvl[j + 1][0]] = 1;
        mat[lvl[j + 1][0]][lvl[j][0]] = 1;
      }
      mat[1][lvl[1][0]] = mat[lvl[1][0]][1] = 1;
      mat[2][lvl[dim][0]] = mat[lvl[dim][0]][2] = 1;
    }
    PR(n);
    for ((i) = 1; (i) <= (int)(n); (i)++) {
      for ((j) = 1; (j) <= (int)(n); (j)++) {
        if (mat[i][j])
          printf("Y");
        else
          printf("N");
      }
      puts("");
    }
  }
  return 0;
}

```