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:
//Author: net12k44
import java.io.*;
import java.util.*;
public
class Main{//}
	
static PrintWriter out;
static char a[][] = new char[1000][1000];
static int d[][] = new int[30][2];

static void solve() {
	int k = in.nextInt();
	for(char A[] : a ) Arrays.fill(A , 'N');
	
	int n = 2;
	int lim = 30;
	d[0][0] = d[0][1] = 0;
	for(int i = 1; i < lim; ++i) {
		d[i][0] = n++;
		d[i][1] = n++;
		for(int j = 0; j<2; ++j)
		for(int J = 0; J<2; ++J) a[ d[i-1][j] ][ d[i][J] ] = a[ d[i][J] ][ d[i-1][j] ] = 'Y';		
	}
	
	for(int i = 0; i < lim; ++i)
		if ( ( k & (1 << i) ) > 0 ) {
			int t = lim-1;
			int now = 1;
			while (t>i) {				
				a[n][now] = a[now][n] = 'Y';
				--t;
				now = n;
				n++;				
			}			
			a[ d[i][0] ][now] = a[now][ d[i][0] ] = 'Y';
			a[ d[i][1] ][now] = a[now][ d[i][1] ] = 'Y';
		
		}
	
	out.println(n);
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) out.print(a[i][j]);
		out.println();
	}
	
	
	
}
	
public static void main (String[] args) throws java.lang.Exception {		
	long startTime = System.currentTimeMillis();

	out = new PrintWriter(System.out);
	solve();	
	//out.println((String.format("%.2f",(double)(System.currentTimeMillis()-startTime)/1000)));
	out.close();
}
	
static class in {
	static BufferedReader reader = new BufferedReader( new InputStreamReader(System.in) ) ;
	static StringTokenizer tokenizer = new StringTokenizer("");				
	static String next() {		
		while ( !tokenizer.hasMoreTokens() )
			try { tokenizer = new StringTokenizer( reader.readLine() ); }
			catch (IOException e){
				throw new RuntimeException(e);			
			}		
		return tokenizer.nextToken();
	}
	static int nextInt() { return Integer.parseInt( next() ); }		
	static double nextDouble(){ return Double.parseDouble( next() ); }
}
//////////////////////////////////////////////////
}//