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

public class Main implements Runnable {

	public void _main() throws IOException {
		int k = nextInt();
		List<Integer> logs = new ArrayList<Integer>();
		int maxLog = 0;
		int log = 0;
		while (k > 0) {
			if (k % 2 == 1) {
				logs.add(log);
				maxLog = Math.max(maxLog, log);
			}
			++log;
			k /= 2;
		}
		if (maxLog == 0) {
			out.println("2");
			out.println("NY");
			out.println("YN");
			return;
		}
		int n = 3;
		addEdge(0, n - 1);
		for (int i = 0; i < maxLog; i++) {
			int a = n - 1;
			int b = n;
			int c = n + 1;
			int d = n + 2;
			addEdge(a, b);
			addEdge(a, c);
			addEdge(d, b);
			addEdge(d, c);
			n += 3;
		}
		addEdge(1, n - 1);		
		for (int i = 0; i < logs.size() - 1; i++) {
			int v = maxLog - logs.get(i);
			addEdge(0, n);
			for (int j = 0; j < 2*v - 1; j++) {
				addEdge(n + j, n + j + 1);
			}			
			n += 2*v;
			addEdge(n - 1, 2 + 3*v);
		}
		boolean[][] adj = new boolean[n][n];
		for (int i = 0; i < as.size(); i++) {
			int a = as.get(i);
			int b = bs.get(i);
			adj[a][b] = true;
			adj[b][a] = true;
			//out.println((a + 1) + " " + (b + 1));
		}
		out.println(n);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				out.print(adj[i][j] ? 'Y' : 'N');				
			}
			out.println();
		}
	}

	List<Integer> as = new ArrayList<Integer>();
	List<Integer> bs = new ArrayList<Integer>();
	void addEdge(int a, int b) {
		as.add(a);
		bs.add(b);
	}
	
	


	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer st;

	private String next() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String rl = in.readLine();
			if (rl == null)
				return null;
			st = new StringTokenizer(rl);
		}
		return st.nextToken();
	}

	private int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	private long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	private double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	public static void main(String[] args) {
		Locale.setDefault(Locale.UK);
		new Thread(new Main()).start();
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			//in = new BufferedReader(new FileReader("a.in"));
			//out = new PrintWriter(new FileWriter("a.out"));

			_main();

			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(202);
		}
	}

}