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.util.*;
import java.io.*;
import java.math.*;

import static java.lang.Math.*;

public class Solution implements Runnable {
	
	public void solve() throws Exception {
		int k = sc.nextInt();
		if (k == 1) {
			out.println(2);
			out.println("NY");
			out.println("YN");
			return;
		}
		
		int ans [][] = new int [1000][1000];
		int finish [] = new int [1000];
		int M = 2;
		int shortLen = 0;
		for (int i = 30; i >= 1; i--) {
			if (((1 << i) & k) != 0) {
				if (M == 2) {
					shortLen = i;
					int start = 0;
					for (int j = 0; j < shortLen; j++) {
						ans[start][M] = 1;
						ans[M][start] = 1;
						M++;
						ans[start][M] = 1;
						ans[M][start] = 1;
						M++;
						if (j == shortLen - 1) {
							ans[M - 1][1] = 1;
							ans[1][M - 1] = 1;
							ans[M - 2][1] = 1;
							ans[1][M - 2] = 1;
						} else {
							M++;
							ans[M - 3][M - 1] = 1;
							ans[M - 1][M - 3] = 1;
							ans[M - 2][M - 1] = 1;
							ans[M - 1][M - 2] = 1;
							finish[shortLen - j - 1] = M - 1;
							start = M - 1;
						}
					}
				} else {
					int start = 0;
					for (int j = 0; j < 2 * (shortLen - i) - 1; j++) {
						ans[start][M] = 1;
						ans[M][start] = 1;
						M++;
						start = M - 1;
					}
					ans[start][finish[i]] = 1;
					ans[finish[i]][start] = 1;
				}
			}
		}
		if ((k & 1) != 0) {
			int start = 0;
			for (int j = 0; j < 2 * shortLen - 1; j++) {
				ans[start][M] = 1;
				ans[M][start] = 1;
				start = M;
				M++;
			}
			ans[start][1] = 1;
			ans[1][start] = 1;
		}
		out.println(M);
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++) {
				if (ans[i][j] == 1) {
					out.print("Y");
				} else {
					out.print("N");
				}
			}
			out.println();
		}
	}


	static Throwable t;

	BufferedReader in;
	FastScanner sc;
	PrintWriter out;

	@Override
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			sc = new FastScanner(in);
			solve();
		} catch (Throwable t) {
			Solution.t = t;
		} finally {
			out.close();
		}
	}

	public static void main(String[] args) throws Throwable {
		Thread thread = new Thread(null, new Solution(), "", 1 << 26);
		thread.start();
		thread.join();
		if (Solution.t != null)
			throw t;
	}

}

class FastScanner {

	BufferedReader in;
	StringTokenizer st;

	public FastScanner(BufferedReader in) {
		this.in = in;
	}

	public String nextToken() throws Exception {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}

	public int nextInt() throws Exception {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws Exception {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws Exception {
		return Double.parseDouble(nextToken());
	}

}