#include <bits/stdc++.h>
using namespace std;
int INK, C = 3;
bool adj[2200][2200];
void join(int i, int j) {
  assert(!adj[i][j]);
  adj[i][j] = adj[j][i] = 1;
}
vector<int> o, nu;
int est(int K, int n = 2) {
  if (n == 2) {
    int cnt = 0, LEN = 2;
    for (int i = 31; i--;)
      if ((1 << i) & K) {
        LEN = max(LEN, i);
        cnt += LEN - (i + 1);
        cnt += i * 2;
      }
    return cnt;
  }
  int cnt = 0;
  int pr = 0;
  vector<int> v;
  while (K) {
    for (int x = (0); x < (K % n); x++) v.push_back(pr);
    K /= n, pr++;
  }
  int LEN = 2;
  reverse(v.begin(), v.end());
  for (int i : v) {
    LEN = max(LEN, i + 1);
    cnt += LEN - (i + 1);
    cnt += i * n;
  }
  return cnt;
}
void go(int K, int INST, int INEN, int n = 2) {
  vector<int> v;
  int pr = 0;
  while (K) {
    for (int x = (0); x < (K % n); x++) v.push_back(pr);
    K /= n, pr++;
  }
  int LEN = 2;
  reverse(v.begin(), v.end());
  for (int i : v) {
    int ST = INST;
    LEN = max(LEN, i + 1);
    for (int rep = (i + 1); rep < (LEN); rep++) join(ST, C), ST = C, C++;
    o.clear();
    o.push_back(ST);
    for (int j = (0); j < (i + 1); j++) {
      nu.clear();
      if (j != i) {
        for (int x = (0); x < (n); x++) nu.push_back(C++);
      } else {
        nu.push_back(INEN);
      }
      for (int b : nu)
        for (int a : o) join(a, b);
      o = nu;
    }
  }
}
int main() {
  scanf("%d", &INK);
  if (est(INK) > 998) {
    bool can = 1;
    int sv = -1;
    for (int d = 1; d * d <= INK; d++)
      if (INK % d == 0) {
        if (est(d) + est(INK / d) + 3 <= 1000) {
          sv = d;
          can = 1;
          break;
        }
      }
    if (can) {
      C++;
      go(sv, 1, 3);
      go(INK / sv, 3, 2);
    } else
      assert(0);
  } else {
    go(INK, 1, 2);
  }
  printf("%d\n", C - 1);
  for (int i = (1); i < (C); i++) {
    for (int j = (1); j < (C); j++) {
      printf(adj[i][j] ? "Y" : "N");
    }
    puts("");
  }
  return 0;
}

### Prompt

Generate 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;
int INK, C = 3;
bool adj[2200][2200];
void join(int i, int j) {
  assert(!adj[i][j]);
  adj[i][j] = adj[j][i] = 1;
}
vector<int> o, nu;
int est(int K, int n = 2) {
  if (n == 2) {
    int cnt = 0, LEN = 2;
    for (int i = 31; i--;)
      if ((1 << i) & K) {
        LEN = max(LEN, i);
        cnt += LEN - (i + 1);
        cnt += i * 2;
      }
    return cnt;
  }
  int cnt = 0;
  int pr = 0;
  vector<int> v;
  while (K) {
    for (int x = (0); x < (K % n); x++) v.push_back(pr);
    K /= n, pr++;
  }
  int LEN = 2;
  reverse(v.begin(), v.end());
  for (int i : v) {
    LEN = max(LEN, i + 1);
    cnt += LEN - (i + 1);
    cnt += i * n;
  }
  return cnt;
}
void go(int K, int INST, int INEN, int n = 2) {
  vector<int> v;
  int pr = 0;
  while (K) {
    for (int x = (0); x < (K % n); x++) v.push_back(pr);
    K /= n, pr++;
  }
  int LEN = 2;
  reverse(v.begin(), v.end());
  for (int i : v) {
    int ST = INST;
    LEN = max(LEN, i + 1);
    for (int rep = (i + 1); rep < (LEN); rep++) join(ST, C), ST = C, C++;
    o.clear();
    o.push_back(ST);
    for (int j = (0); j < (i + 1); j++) {
      nu.clear();
      if (j != i) {
        for (int x = (0); x < (n); x++) nu.push_back(C++);
      } else {
        nu.push_back(INEN);
      }
      for (int b : nu)
        for (int a : o) join(a, b);
      o = nu;
    }
  }
}
int main() {
  scanf("%d", &INK);
  if (est(INK) > 998) {
    bool can = 1;
    int sv = -1;
    for (int d = 1; d * d <= INK; d++)
      if (INK % d == 0) {
        if (est(d) + est(INK / d) + 3 <= 1000) {
          sv = d;
          can = 1;
          break;
        }
      }
    if (can) {
      C++;
      go(sv, 1, 3);
      go(INK / sv, 3, 2);
    } else
      assert(0);
  } else {
    go(INK, 1, 2);
  }
  printf("%d\n", C - 1);
  for (int i = (1); i < (C); i++) {
    for (int j = (1); j < (C); j++) {
      printf(adj[i][j] ? "Y" : "N");
    }
    puts("");
  }
  return 0;
}

```