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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class D228 {
	public static void main(String[] args) {
		FS scan = new FS(System.in);
		boolean[][] adj = new boolean[1000][1000];
		
		int[] pow = new int[30];
		int[] powEnd = new int[30];
		int idx = 2;
		for(int i=29;i>0;i--){
			pow[i] = idx;
			for(int j=0;j<2*i-2;j+=2){
				adj[idx+j][idx+j+2] = true;
				adj[idx+j][idx+j+3] = true;
				adj[idx+j+1][idx+j+2] = true;
				adj[idx+j+1][idx+j+3] = true;
			}
			adj[idx+2*i-2][1] = true;
			adj[idx+2*i-1][1] = true;
			idx+=2*i;
		}
		pow[0] = idx;
		for(int i=idx;i<idx+28;i++){
			adj[i][i+1] = true;
		}adj[idx+28][1] = true;
		idx+=29;
		adj[0][idx] = true;
		int K = scan.nextInt();
		if((K&1)!=0)adj[0][pow[0]]=true;
		for(int i=idx;i<idx+29;i++){
			adj[i][i+1] = true;
			int a = 29 - (i-idx+1);
			if(a==0)break;
			if((K&(1<<a))!=0){
				adj[i][pow[a]]=true;
				adj[i][pow[a]+1]=true;
			}
		}
		if((K&(1<<29))!=0){
			adj[0][pow[29]]=true;
			adj[0][pow[29]+1]=true;
		}
		print(adj);
		
//		int[][] d = new int[1000][1000];
//		for(int i=0;i<1000;i++)
//			for(int j=0;j<1000;j++)
//				d[i][j] = d[j][i] = (adj[i][j]||adj[j][i])?1:1000000;
//		for(int i=0;i<1000;i++)d[i][i] = 0;
//		for(int k=0;k<1000;k++)
//			for(int i=0;i<1000;i++)
//				for(int j=0;j<1000;j++)
//					if(d[i][j]>d[i][k]+d[k][j])d[i][j] = d[i][k]+d[k][j];
//		
//		System.out.println(d[0][1]);
	}
	private static void print(boolean[][] adj) {
		PrintWriter out = new PrintWriter(System.out);
		out.println(1000);
		for(int i=0;i<1000;i++){
			for(int j=0;j<1000;j++){
				out.print((adj[i][j]||adj[j][i])?"Y":"N");
			}out.println();
		}
		out.close();
	}
	private static class FS {
		BufferedReader br;
		StringTokenizer st;
		public FS(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}
		String next(){
			while(st==null||!st.hasMoreElements()){
				try{st = new StringTokenizer(br.readLine());}
				catch(IOException e){e.printStackTrace();}
			}
			return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());}
		double nextDouble() { return Double.parseDouble(next());}
	}
}