#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int n;
int adj[2002][2002];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  cin >> n;
  if (n == 1) {
    cout << 2 << '\n';
    cout << "NY\n";
    cout << "YN\n";
    return 0;
  }
  int len = 0;
  int nr = 2;
  int cr = 2;
  int xtr = 0;
  for (int i = 30; i >= 0; --i) {
    if (n & (1 << i)) {
      int nr = 2 * i;
      len = max(len, nr / 4 + (nr % 4 > 0));
    }
  }
  for (int i = 30; i >= 0; --i)
    if (n & (1 << i)) {
      int nrv = 2 * i;
      vector<int> v;
      v.push_back(1);
      int LL = 0;
      while (nrv) {
        int j;
        if (nrv >= 4)
          j = 4;
        else
          j = 2;
        nrv -= j;
        ++LL;
        vector<int> v2;
        for (int k = 1; k <= j; ++k) v2.push_back(++cr);
        for (int R = 0; R < v.size(); ++R)
          for (int S = 0; S < v2.size(); ++S)
            adj[v[R]][v2[S]] = adj[v2[S]][v[R]] = 1;
        v.clear();
        v = v2;
      }
      while (LL < len) {
        vector<int> v2;
        v2.push_back(++cr);
        for (int R = 0; R < v.size(); ++R) adj[v[R]][cr] = adj[cr][v[R]] = 1;
        v.clear();
        ++LL;
        v = v2;
      }
      for (int R = 0; R < v.size(); ++R) adj[v[R]][2] = adj[2][v[R]] = 1;
    }
  if (cr > 1000) {
    int xtr = 0;
    while (1) {
      ++xtr;
      --n;
      vector<int> divi;
      int n2 = n;
      int nr = 1;
      int sum = 0;
      for (int i = 2; i * i <= n2; ++i)
        while (n2 % i == 0) divi.push_back(i), n2 /= i, nr *= i, sum += i;
      if (n2 > 1) nr *= n2, divi.push_back(n2), sum += n2;
      if (xtr * divi.size() + sum <= 998) {
        memset(adj, 0, sizeof(adj));
        cr = 2;
        for (int i = 1; i <= xtr; ++i) {
          int lst = 1;
          for (int j = 1; j <= divi.size(); ++j) {
            ++cr;
            adj[lst][cr] = adj[cr][lst] = 1;
            lst = cr;
          }
          adj[lst][2] = adj[2][lst] = 1;
        }
        vector<int> v;
        v.push_back(1);
        for (int aa = 0; aa < divi.size(); ++aa) {
          int j = divi[aa];
          vector<int> v2;
          for (int k = 1; k <= j; ++k) v2.push_back(++cr);
          for (int R = 0; R < v.size(); ++R)
            for (int S = 0; S < v2.size(); ++S)
              adj[v[R]][v2[S]] = adj[v2[S]][v[R]] = 1;
          v.clear();
          v = v2;
        }
        for (int R = 0; R < v.size(); ++R) adj[v[R]][2] = adj[2][v[R]] = 1;
        break;
      }
    }
  }
  cout << cr << '\n';
  for (int i = 1; i <= cr; cout << '\n', ++i)
    for (int j = 1; j <= cr; ++j)
      if (adj[i][j])
        cout << "Y";
      else
        cout << "N";
  return 0;
}

### Prompt

Create a solution in Cpp for 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>
#pragma GCC optimize("O3")
using namespace std;
int n;
int adj[2002][2002];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  cin >> n;
  if (n == 1) {
    cout << 2 << '\n';
    cout << "NY\n";
    cout << "YN\n";
    return 0;
  }
  int len = 0;
  int nr = 2;
  int cr = 2;
  int xtr = 0;
  for (int i = 30; i >= 0; --i) {
    if (n & (1 << i)) {
      int nr = 2 * i;
      len = max(len, nr / 4 + (nr % 4 > 0));
    }
  }
  for (int i = 30; i >= 0; --i)
    if (n & (1 << i)) {
      int nrv = 2 * i;
      vector<int> v;
      v.push_back(1);
      int LL = 0;
      while (nrv) {
        int j;
        if (nrv >= 4)
          j = 4;
        else
          j = 2;
        nrv -= j;
        ++LL;
        vector<int> v2;
        for (int k = 1; k <= j; ++k) v2.push_back(++cr);
        for (int R = 0; R < v.size(); ++R)
          for (int S = 0; S < v2.size(); ++S)
            adj[v[R]][v2[S]] = adj[v2[S]][v[R]] = 1;
        v.clear();
        v = v2;
      }
      while (LL < len) {
        vector<int> v2;
        v2.push_back(++cr);
        for (int R = 0; R < v.size(); ++R) adj[v[R]][cr] = adj[cr][v[R]] = 1;
        v.clear();
        ++LL;
        v = v2;
      }
      for (int R = 0; R < v.size(); ++R) adj[v[R]][2] = adj[2][v[R]] = 1;
    }
  if (cr > 1000) {
    int xtr = 0;
    while (1) {
      ++xtr;
      --n;
      vector<int> divi;
      int n2 = n;
      int nr = 1;
      int sum = 0;
      for (int i = 2; i * i <= n2; ++i)
        while (n2 % i == 0) divi.push_back(i), n2 /= i, nr *= i, sum += i;
      if (n2 > 1) nr *= n2, divi.push_back(n2), sum += n2;
      if (xtr * divi.size() + sum <= 998) {
        memset(adj, 0, sizeof(adj));
        cr = 2;
        for (int i = 1; i <= xtr; ++i) {
          int lst = 1;
          for (int j = 1; j <= divi.size(); ++j) {
            ++cr;
            adj[lst][cr] = adj[cr][lst] = 1;
            lst = cr;
          }
          adj[lst][2] = adj[2][lst] = 1;
        }
        vector<int> v;
        v.push_back(1);
        for (int aa = 0; aa < divi.size(); ++aa) {
          int j = divi[aa];
          vector<int> v2;
          for (int k = 1; k <= j; ++k) v2.push_back(++cr);
          for (int R = 0; R < v.size(); ++R)
            for (int S = 0; S < v2.size(); ++S)
              adj[v[R]][v2[S]] = adj[v2[S]][v[R]] = 1;
          v.clear();
          v = v2;
        }
        for (int R = 0; R < v.size(); ++R) adj[v[R]][2] = adj[2][v[R]] = 1;
        break;
      }
    }
  }
  cout << cr << '\n';
  for (int i = 1; i <= cr; cout << '\n', ++i)
    for (int j = 1; j <= cr; ++j)
      if (adj[i][j])
        cout << "Y";
      else
        cout << "N";
  return 0;
}

```