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.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.Random;
import java.util.StringTokenizer;

public class Main {

    String fileName = "";
    //////////////////////    SOLUTION   SOLUTION  SOLUTION    //////////////////////////////
    Long INF = Long.MAX_VALUE;
    int MODULO = 1000_000_000 + 7;
    int MAX_VALUE = 1000_1000;
    int[][] steps = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    private final static Random rnd = new Random();
    double eps = 1e-4;

    class Sum implements Comparable<Sum>{
        int sum;
        int ind1, ind2;

        public Sum(int sum, int ind1, int ind2) {
            this.sum = sum;
            this.ind1 = ind1;
            this.ind2 = ind2;
        }

        @Override
        public int compareTo(Sum o) {
            return Integer.compare(this.sum, o.sum);
        }
    }
    int[][] nextRems;
    void solve() throws IOException {
        int n = readInt();
        int[] arr = readIntArray(n);
        int count = 0;
        for (int i=0; i<n; ++i){
            if (gcd(arr[i], i+1==n?1:arr[i+1]) != 1){
                count++;
            };
        }
        out.println(count);
        for (int i=0; i<n; ++i){
            out.print(arr[i]+" ");
            if (gcd(arr[i], i+1==n?1:arr[i+1]) != 1) out.print(1+" ");
        }
    }

    class Point{
        long x, y;

        public Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    class Fenwik {
        int[] t;
        int n;
        Fenwik(int n){
            t = new int[n];
            this.n = n;
        }

        void inc(int r, int delta){
            for (; r < n; r = r | (r + 1)) t[r] += delta;
        }
        int getSum(int r){
            int res = 0;
            for (; r >=0; r = (r & (r + 1) ) - 1) res += t[r];
            return res;
        }
    }
    boolean isPrime(int n){
        for (int i=2; i*i<=n; ++i){
            if (n%i==0) return false;
        }
        return true;
    }
    class Edge implements Comparable<Edge>{
        int from, to, num, dist;
        Edge(int from, int to, int dist, int num){
            this.from = from;
            this.to = to;
            this.num = num;
            this.dist = dist;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.dist, o.dist);
        }
    }


    class Segment{
        Point p1, p2;
        public Segment(Point p1, Point p2) {
            this.p1 = p1;
            this.p2 = p2;
        }
    }
    Point readPoint() throws IOException{
        return new Point(readInt(), readInt());
    }
    class Number implements Comparable<Number>{
        int x, cost;
        Number(int x, int cost){
            this.x = x;
            this.cost = cost;
        }

        @Override
        public int compareTo(Number o) {
            return Integer.compare(this.cost, o.cost);
        }
    }

    void readUndirectedGraph (int n, int m, int[][] graph) throws IOException{
        Edge[] edges = new Edge[m];
        int[] countEdges = new int[n];
        for (int i=0; i<m; ++i){
            int from = readInt() - 1;
            int to = readInt() - 1;
            countEdges[from]++;
            countEdges[to]++;
            edges[i] = new Edge(from, to, 0, 0);
        }
        for (int i=0; i<n; ++i) {
            graph[i] = new int[countEdges[i]];
        }
        for (int i=0; i<m; ++i){
            graph[edges[i].from][--countEdges[edges[i].from]] = edges[i].to;
            graph[edges[i].to][-- countEdges[edges[i].to]] = edges[i].from;
        }
    }
    class Vertex implements Comparable<Vertex>{
        int i, j, plus;
        Vertex(int i, int j, int plus){
            this.i = i;
            this.j = j;
            this.plus = plus;
        }

        @Override
        public int compareTo(Vertex o) {
            return Integer.compare(this.plus, o.plus);
        }
    }



    ///////////////////////////////////////////////////////////////////////////////////////////

    class Dsu{
        int[] parent;
        int countSets;
        Dsu(int n){
            parent = new int[n];
            countSets = n;
            for (int i=0; i<n; ++i){
                parent[i] = i;
            }
        }
        int findSet(int a){
            if (a == parent[a]) return a;
            parent[a] = findSet(parent[a]);
            return parent[a];
        }
        void unionSets(int a, int b){
            a = findSet(a);
            b = findSet(b);
            if (a != b){
                parent[a] = b;
                countSets--;
            }
        }
    }

    class SparseTable{
        int[][] rmq;
        int[] logTable;
        int n;
        SparseTable(int[] a){
            n = a.length;
            logTable = new int[n+1];
            for(int i = 2; i <= n; ++i){
                logTable[i] = logTable[i >> 1] + 1;
            }
            rmq = new int[logTable[n] + 1][n];
            for(int i=0; i<n; ++i){
                rmq[0][i] = a[i];
            }

            for(int k=1; (1 << k) < n; ++k){
                for(int i=0; i + (1 << k) <= n; ++i){
                    int max1 = rmq[k - 1][i];
                    int max2 = rmq[k-1][i + (1 << (k-1))];
                    rmq[k][i] = Math.max(max1, max2);
                }
            }
        }

        int max(int l, int r){
            int k = logTable[r - l];
            int max1 = rmq[k][l];
            int max2 = rmq[k][r - (1 << k) + 1];
            return Math.max(max1, max2);
        }
    }
    long checkBit(long mask, int bit){
        return (mask >> bit) & 1;
    }

    static int checkBit(int mask, int bit) {
        return (mask >> bit) & 1;
    }
    boolean isLower(char c){
        return c >= 'a' && c <= 'z';
    }

    ////////////////////////////////////////////////////////////



    int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a%b);
    }
    long gcd(long a, long b){
        return b == 0 ? a : gcd(b, a%b);
    }
    double binPow(double a, int pow){
        if (pow == 0) return 1;
        if (pow % 2 == 1) {
            return a * binPow(a, pow - 1);
        } else {
            double c = binPow(a, pow / 2);
            return c * c;
        }
    }
    long binPow(long a, long b, long m) {
        if (b == 0) {
            return 1;
        }
        if (b % 2 == 1) {
            return ((a % m) * (binPow(a, b - 1, m) % m)) % m;
        } else {
            long c = binPow(a, b / 2, m);
            return (c * c) % m;
        }

    }
    int minInt(int... values) {
        int min = Integer.MAX_VALUE;
        for (int value : values) min = Math.min(min, value);
        return min;
    }

    int maxInt(int... values) {
        int max = Integer.MIN_VALUE;
        for (int value : values) max = Math.max(max, value);
        return max;
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        new Main().run();
    }

    void run() throws NumberFormatException, IOException {
        solve();
        out.close();
    };

    BufferedReader in;
    PrintWriter out;

    StringTokenizer tok;
    String delim = " ";

    Main() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }

        }
        tok = new StringTokenizer("");
    }

    String readLine() throws IOException {
        return in.readLine();
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) {
                return null;
            }

            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken();
    }

    int readInt() throws NumberFormatException, IOException {
        return Integer.parseInt(readString());
    }
    byte readByte() throws NumberFormatException, IOException {
        return Byte.parseByte(readString());
    }
    int[] readIntArray (int n) throws NumberFormatException, IOException {
        int[] a = new int[n];
        for(int i=0; i<n; ++i){
            a[i] = readInt();
        }
        return a;
    }

    Integer[] readIntegerArray (int n) throws NumberFormatException, IOException {
        Integer[] a = new Integer[n];
        for(int i=0; i<n; ++i){
            a[i] = readInt();
        }
        return a;
    }

    long readLong() throws NumberFormatException, IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(readString());
    }
}