#include <bits/stdc++.h>
using namespace std;
int bmwp[100];
int pow2[100];
vector<int> ans;
vector<int>::iterator it;
map<int, int> my_hash;
int shortest;
int id;
const int S = 1;
const int T = 2;
bool grid[1008][1008];
void make_line(int dot, int type) {
  vector<pair<int, int> > me;
  vector<pair<int, int> >::iterator it;
  me.clear();
  for (int i = 1; i <= dot; i++) {
    me.push_back(make_pair(id, id + 1));
    id += 2;
  }
  if (type == 1 && dot != shortest) {
    my_hash.clear();
    for (int i = dot + 1; i <= shortest; i++) {
      me.push_back(make_pair(id, id));
      my_hash[i] = id;
      id += 1;
    }
  }
  it = me.begin();
  grid[S][it->first] = grid[S][it->second] = 1;
  grid[it->first][S] = grid[it->second][S] = 1;
  if (type == 1 && dot != shortest) {
    it = me.end() - 1;
    grid[it->first][T] = grid[it->second][T] = 1;
    grid[T][it->first] = grid[T][it->second] = 1;
  } else {
    it = me.end() - 1;
    int v = (dot == shortest ? T : my_hash[dot + 1]);
    grid[it->first][v] = grid[it->second][v] = 1;
    grid[v][it->first] = grid[v][it->second] = 1;
  }
  for (int i = 1; i < me.size(); i++) {
    int u1 = me[i - 1].first;
    int u2 = me[i - 1].second;
    int v1 = me[i].first;
    int v2 = me[i].second;
    grid[u1][v1] = grid[u1][v2] = 1;
    grid[u2][v1] = grid[u2][v2] = 1;
    grid[v1][u1] = grid[v1][u2] = 1;
    grid[v2][u1] = grid[v2][u2] = 1;
  }
}
void output() {
  int n = id - 1, i, j;
  cout << n << endl;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) printf("%s", grid[i][j] ? "Y" : "N");
    puts("");
  }
}
int main() {
  int i, k, sum = 0;
  pow2[0] = 1;
  for (i = 1; i <= 30; i++) pow2[i] = pow2[i - 1] * 2;
  cin >> k;
  if (k == 1) {
    puts("2");
    puts("NY");
    puts("YN");
    return 0;
  }
  ans.clear();
  for (i = 30; i >= 0; i--) {
    if (k >= pow2[i]) {
      ans.push_back(i);
      k -= pow2[i];
    }
  }
  memset(grid, 0, sizeof(grid));
  shortest = *ans.begin();
  id = 3;
  make_line(ans[ans.size() - 1], 1);
  for (i = ans.size() - 2; i >= 0; i--) make_line(ans[i], 0);
  output();
  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>
using namespace std;
int bmwp[100];
int pow2[100];
vector<int> ans;
vector<int>::iterator it;
map<int, int> my_hash;
int shortest;
int id;
const int S = 1;
const int T = 2;
bool grid[1008][1008];
void make_line(int dot, int type) {
  vector<pair<int, int> > me;
  vector<pair<int, int> >::iterator it;
  me.clear();
  for (int i = 1; i <= dot; i++) {
    me.push_back(make_pair(id, id + 1));
    id += 2;
  }
  if (type == 1 && dot != shortest) {
    my_hash.clear();
    for (int i = dot + 1; i <= shortest; i++) {
      me.push_back(make_pair(id, id));
      my_hash[i] = id;
      id += 1;
    }
  }
  it = me.begin();
  grid[S][it->first] = grid[S][it->second] = 1;
  grid[it->first][S] = grid[it->second][S] = 1;
  if (type == 1 && dot != shortest) {
    it = me.end() - 1;
    grid[it->first][T] = grid[it->second][T] = 1;
    grid[T][it->first] = grid[T][it->second] = 1;
  } else {
    it = me.end() - 1;
    int v = (dot == shortest ? T : my_hash[dot + 1]);
    grid[it->first][v] = grid[it->second][v] = 1;
    grid[v][it->first] = grid[v][it->second] = 1;
  }
  for (int i = 1; i < me.size(); i++) {
    int u1 = me[i - 1].first;
    int u2 = me[i - 1].second;
    int v1 = me[i].first;
    int v2 = me[i].second;
    grid[u1][v1] = grid[u1][v2] = 1;
    grid[u2][v1] = grid[u2][v2] = 1;
    grid[v1][u1] = grid[v1][u2] = 1;
    grid[v2][u1] = grid[v2][u2] = 1;
  }
}
void output() {
  int n = id - 1, i, j;
  cout << n << endl;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) printf("%s", grid[i][j] ? "Y" : "N");
    puts("");
  }
}
int main() {
  int i, k, sum = 0;
  pow2[0] = 1;
  for (i = 1; i <= 30; i++) pow2[i] = pow2[i - 1] * 2;
  cin >> k;
  if (k == 1) {
    puts("2");
    puts("NY");
    puts("YN");
    return 0;
  }
  ans.clear();
  for (i = 30; i >= 0; i--) {
    if (k >= pow2[i]) {
      ans.push_back(i);
      k -= pow2[i];
    }
  }
  memset(grid, 0, sizeof(grid));
  shortest = *ans.begin();
  id = 3;
  make_line(ans[ans.size() - 1], 1);
  for (i = ans.size() - 2; i >= 0; i--) make_line(ans[i], 0);
  output();
  return 0;
}

```