Problem: You are given an array of n elements, you must make it a co-prime array in as few moves as possible.

In each move you can insert any positive integral number you want not greater than 109 in any place in the array.

An array is co-prime if any two adjacent numbers of it are co-prime.

In the number theory, two integers a and b are said to be co-prime if the only positive integer that divides both of them is 1.

Input

The first line contains integer n (1 ≤ n ≤ 1000) — the number of elements in the given array.

The second line contains n integers ai (1 ≤ ai ≤ 109) — the elements of the array a.

Output

Print integer k on the first line — the least number of elements needed to add to the array a to make it co-prime.

The second line should contain n + k integers aj — the elements of the array a after adding k elements to it. Note that the new array should be co-prime, so any two adjacent values should be co-prime. Also the new array should be got from the original array a by adding k elements to it.

If there are multiple answers you can print any one of them.

Example

Input

3
2 7 28


Output

1
2 7 9 28

Solution (in JAVA):

Solution:
import java.io.FileInputStream;
import java.io.*;
import java.util.Locale;
import java.util.StringTokenizer;


public class Task_Rnd600_A {

	final static String input_file_name = "input/Rnd600_A.txt";
	
	public static void main(String[] args)
	{
		//!!!!!!!!!!111
		reader.init(true);		//to server
		//reader.init(false);
		
		run();
		wr.flush();
	}
	
	static int pp[] = new int[3500];
	static int pcnt = 0;
	
	public static void gen_primes() {

		pp[pcnt++] = 2;
		
		int dd = (int)Math.sqrt(1000000000);
		for (int ii = 3; ii < dd; ii += 2) {
			int d2 = (int)Math.sqrt(ii);
			for (int jj= 0; jj < pcnt; jj++) {
				if (pp[jj] > d2) {
					break;
				}
				if (ii % pp[jj] == 0) {
					d2 = -1;
					break;
				}
			}
			if (d2 != -1)
				pp[pcnt++] = ii;
		}
		
	}

	public static boolean primed(int x1, int x2) {
		
		if (x1 == 1 || x2 == 1)
			return true;
		
		if (x1 % x2 == 0 || x2 % x1 == 0)
			return false;
		
		if(x1 > x2) {
			int tt = x1; x1 = x2; x2 = tt; 
		}
		
		int d1 = (int)Math.sqrt(x1) + 10;
		
		for (int ii = 0; ii < pcnt; ii++) {
			if (x1 % pp[ii] == 0 && (x2 % pp[ii] == 0 || x1 != pp[ii] && x2 % (x1 / pp[ii]) == 0))
				return false;
			if (pp[ii] > d1)
				break;
		}
		
		return true;
	}
	
    public static void run()
    {
    	gen_primes();
    	
		int n = reader.nextInt();
		int aa[] = new int[n];
		for (int i = 0; i < n; i++)
			aa[i] = reader.nextInt();

		int bb[] = new int[n];
		int bcnt = 0;
		
		for (int ii = 0; ii < n-1; ii++) {
			if (!primed(aa[ii], aa[ii+1])) {
				bcnt++;
				bb[ii] = 1;
			}
				
		}
		
		wr.print(bcnt);
		wr2.endl();
		for (int ii = 0; ii < n-1; ii++) {
			wr.print(aa[ii]);
			wr.print(' ');
			
			if (bb[ii] != 0) {
				wr.print(1);
				wr.print(' ');
			}
				
		}
		wr.print(aa[n-1]);
		wr2.endl();
    }
	
    public static void run_slow()
    {
		int n = reader.nextInt();
		int aa[] = new int[n];
		
		for (int i = 0; i < n; i++)
			aa[i] = reader.nextInt();
		
		int bb[] = new int[n];
		for(int i = 0; i < n; i++)
			bb[i] = aa[i];


		for (int i = 0; i < n; i++)
		{
			int g = n - i;

			int max = -1;
			for (int j = 0; j < g; j++)
			{
				if (aa[j+i] < bb[j])
					bb[j] = aa[j+i];
				if (bb[j] > max)
					max = bb[j];
			}
		
			if (i > 0)
				wr.print(' ');
			wr.print(max);
		}
		

		wr2.endl();
	}

    
    static public PrintWriter wr; 
    static OutputWriter wr2=new OutputWriter(System.out);
	static class reader{
		static BufferedReader br; static StringTokenizer tkn;
		static String readln() { try { return br.readLine(); } catch (Exception e) { return ""; } }
		static void init(boolean console) {
			if (console) { br=new BufferedReader(new InputStreamReader(System.in)); }
			else { try { br=new BufferedReader(new InputStreamReader(new FileInputStream(input_file_name))); }
				catch (Exception e) { System.exit(551); } }
			tkn=new StringTokenizer("");
		}
		static String next() { while (!tkn.hasMoreTokens()){ tkn=new StringTokenizer(readln()); } return tkn.nextToken(); }
		static int nextInt(){ while (!tkn.hasMoreTokens()){ tkn=new StringTokenizer(readln()); } return Integer.parseInt(tkn.nextToken()); }
		static long nextLong(){ while (!tkn.hasMoreTokens()){ tkn=new StringTokenizer(readln()); } return Long.parseLong(tkn.nextToken()); }
		static double nextDouble(){ while (!tkn.hasMoreTokens()){ tkn=new StringTokenizer(readln()); } return Double.parseDouble(tkn.nextToken()); }
	}
    static class OutputWriter {
        OutputWriter(OutputStream stream) { wr = new PrintWriter(stream); }
        public void printf(String format, Object... args) { wr.print(String.format(Locale.ENGLISH, format, args)); }
        public void endl() { wr.print("\n"); }
    }
}