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 10^9 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 a_{i} (1 ≤ a_{i} ≤ 10^9) — 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 a_{j} — 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

Difficulty: interview

Starter code:

Solutions:
import fractions

n = int(input())
A = [int(x) for x in input().split()]
B = []
for i in range(n-1):
    B.append(A[i])
    if fractions.gcd(A[i], A[i+1]) != 1:
        B.append(1)
B.append(A[-1])
print(len(B) - n)
print(' '.join(map(str, B)))




from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
prev = a[0]
k = 0
for c in a[1:]:
    if gcd(prev, c) != 1:
        k += 1
    prev = c
print(k)
prev = a[0]
for c in a[1:]:
    print(prev, end=' ')
    if gcd(prev, c) != 1:
        print(1, end=' ')
    prev = c
print(prev)


#!/usr/bin/env python3

from fractions import gcd

try:
    while True:
        n = int(input())
        a = list(map(int, input().split()))
        result = [a[0]]
        for x in a[1:]:
            if gcd(x, result[-1]) != 1:
                result.append(1)
            result.append(x)
        print(len(result) - len(a))
        print(' '.join(map(str, result)))

except EOFError:
    pass


n = int(input())
a = [int(i) for i in input().split()]
c = 0
i = 0
while i < n - 1:
    x = a[i]
    y = a[i + 1]
    while y > 0:
        x, y = y, x % y
    if x > 1:
        a = a[:i + 1] + [1] + a[i + 1:]
        i += 2
        c += 1
        n += 1
    else:
        i += 1
print(c)
print(*a)

from fractions import gcd


def is_co_prime(x, y):
    return gcd(x, y) != 1


def solve():
    N = int(input())
    L = list(map(int, input().split()))

    ans = [str(L[0])]

    x = 0
    for i in range(1, N):
        if is_co_prime(L[i], L[i - 1]):
            x += 1
            ans.append('1')
        ans.append(str(L[i]))

    print(x)
    print(' '.join(ans))


def __starting_point():
    solve()

__starting_point()

def mp():  return list(map(int,input().split()))
def lt():  return list(map(int,input().split()))
def pt(x):  print(x)
def ip():  return input()
def it():  return int(input())
def sl(x):  return [t for t in x]
def spl(x): return x.split()
def aj(liste, item): liste.append(item)
def bin(x):  return "{0:b}".format(x)

n = it()
L = lt()
def gcd(x,y):
    if x % y == 0:
        return y
    else:
        return gcd(y,x%y)
c = 0
i = 0
while i+1 < len(L):
    d = gcd(L[i],L[i+1])
    if d != 1:
        L.insert(i+1,1)
        c += 1
    i += 1
print(c)
print(' '.join([str(x) for x in L]))
        


from fractions import gcd
n, a, v = int(input()), list(map(int, input().split())), []
for i, ai in enumerate(a):
    v.append(ai)
    if i < n - 1 and gcd(ai, a[i + 1]) > 1:
        v.append(1)
print(len(v) - len(a))
print(' '.join(map(str, v)))

def gcd(a, b):
    if b == 0: return a
    else: return gcd(b, a % b)
def __starting_point():
    n = int(input())
    A = list(map(int, input().split()))
    ans, cnt = [A[0]], 0
    for i in range(1, n):
        if gcd(A[i], A[i - 1]) != 1:
            ans.append(1)
            cnt += 1
        ans.append(A[i])
    print(cnt)
    print(' '.join(str(i) for i in ans))        
__starting_point()

n = int(input())
a = [int(s) for s in input().split()]

def evklid(a, b):
    while a!=0 and b!=0:
        if a > b:
            a = a % b
        else:
            b = b % a
    return a + b


s = ''
k = 0
s += str(a[0])
for i in range(1, n):
    if evklid(a[i], a[i-1]) != 1:
        k += 1
        s += ' 1 ' + str(a[i])
    else:
        s += ' ' + str(a[i])
print(k)
print(s)


def prost(a, b):
	a, b = max(a, b), min(a,b)
	while b!=0:
		a = a%b
		a, b = b, a
	if a==1:
		return (0)
	else:
		return (1)

n = int(input())
s = input().split()
k = 0
for i in range(len(s)-1):
	if prost(int(s[i]), int(s[i+1]))==1: 
		s[i] = s[i] + ' ' + '1'
		k = k+1
print (k)
print (' '.join(x for x in s))

input()


def nod(a, b):
    while b:
        a, b = b, a % b
    return a


def main():
    a = list(map(int, input().split()))
    out = []
    k = 0
    for i in range(0, len(a)-1):
        out.append(a[i])
        if nod(a[i], a[i+1]) != 1:
            out.append(1)
            k += 1
    out.append(a[len(a)-1])
    str_out = " ".join(map(str, out))
    print(k)
    print(str_out)

main()


from math import gcd

n = int(input())
arr = list(map(int, input().split(' ')))
arr2 = []

for i in range(len(arr)-1):
  if not gcd(arr[i], arr[i+1]) == 1:
    #print (arr[i], arr[i+1], gcd(arr[i], arr[i+1]))
    arr2.append(str(arr[i]))
    arr2.append(str(1))
  else:
    arr2.append(str(arr[i]))

arr2.append(str(arr[-1]))

print(len(arr2)-len(arr))
print(' '.join(arr2))


from fractions import gcd
n = int(input())
l = list(map(int, input().split()))
ans = 0
new = [l[0]]
for i in range(1, n):
    if gcd(l[i], l[i - 1]) != 1:
        ans += 1
        new.append(1)
    new.append(l[i])
print(ans)
print(*new)

from fractions import gcd
n=int(input())
count=0
ip=list(map(int,input().split()))
op=[ip[0]]
if n==1:
    print(0)
    print(ip[0])
else:
    for i in range(n-1):
        if gcd(ip[i],ip[i+1])!=1:
            for j in range(2,100000000):
                if gcd(ip[i],j)==1 and gcd(ip[i+1],j)==1:
                    op.append(j)
                    op.append(ip[i+1])                
                    count+=1
                    break
        else:
            op.append(ip[i+1])
    print(count)
    for i in op:
        print(i,end=' ')


def gcd(x, y):
    if x < y:
        t = x
        x = y
        y = t
    if x%y == 0:
        return y
    else:
        return gcd(y, x%y)

n = int(input())
a = input().split()
for i in range(n):
    a[i] = int(a[i])
b = [a[0]]
k = 0
for i in range(1, n):
    if gcd(a[i-1], a[i]) != 1:
        b.append(1)
        k += 1
    b.append(a[i])
s = str(b[0])
for i in range(1, len(b)):
    s += ' ' + str(b[i])
print(k)
print(s)


n=int(input())
l=list(map(int,input().split()))
ans=[str(l[0])]
def gcd(a,b): 
  while b: a,b=b,a%b
  return a
for i in range(1,n): 
  if gcd(l[i],l[i-1])>1: ans+=["1"]
  ans+=[str(l[i])]
print(len(ans)-n)
print(' '.join(ans))

n = int(input())
mass = list(map(int, input().split()))

def gcd(a, b):
    if b:
        return(gcd(b, a % b))
    else:
        return a

#def add(a, b):
    #k = 1
    #while gcd(k, a) != 1
#print(tmp_mass)
i = 0
c = len(mass)
count = 0
while i < c - 1:
    #print(i, c)
    k = gcd(mass[i], mass[i + 1])
    if k == 1:
        i+= 1
        continue
    else:
        count += 1
        mass.insert(i+1, 1)
        c += 1
        i += 2
print(count)
print(' '.join(map(str, mass)))


n = int(input())
mass = list(map(int, input().split()))

def gcd(a, b):
    if b:
        return(gcd(b, a % b))
    else:
        return a
i = 0
c = len(mass)
count = 0
while i < c - 1:
    k = gcd(mass[i], mass[i + 1])
    if k == 1:
        i+= 1
        continue
    else:
        count += 1
        mass.insert(i+1, 1)
        c += 1
        i += 2
print(count)
print(' '.join(map(str, mass)))


import math
ans=[]
count=0
n=int(input())
a=list(map(int,input().split()))
if n==1:
    print(0)
    print(a[0])
    return
    

for i in range(n-1):
    ans.append(str(a[i]))
    if math.gcd(a[i],a[i+1])!=1:
        count +=1
        ans.append('1')


ans.append(str(a[i+1]))
print(count)
print(' '.join(ans))


    



import math
n=int(input())
mas=[int(c) for c in  input().split()]
l=[]
m=mas[0]
for i in range(n-1):
    if math.gcd(mas[i],mas[i+1])!=1:
        l.append(i+1)
       # print(l)
for i in l[::-1]:
    mas.insert(i,1)
k=len(mas)-n
print(k)
for i in mas:
    print(i,end=' ')



import fractions
import sys
n=int(input())
l=list(map(int,input().split()))
ans=[]
for i in range(1,n):
    ans.append(l[i-1])
    if fractions.gcd(l[i],l[i-1])>1:
        ans.append("1")
ans.append(l[n-1])
print(len(ans)-n)
for i in ans:
    sys.stdout.write(str(i)+" ")




def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)
    
    
n = int(input())

a = list(map(int, input().split()))


last = 1
ans = []

for i in range(n):
    if gcd(a[i], last) != 1:
        ans.append(1)
    ans.append(a[i])
    last = a[i]


print(len(ans) - n)

for i in range(len(ans) - 1):
    print(ans[i], end = ' ')


print(ans[len(ans) - 1])




    
    






from math import sqrt
n=int(input())
a=[int(i) for i in input().split()]
insert=[0]*n
ans=[]
cnt=0

def is_co_prime(A,B) :
    t=A%B
    if t==0 :
        return B==1,B
    while True :
        A,B=B,t
        if A%B :
            t=A%B
        else :
            C=B
            break
    return C==1,C

for i in range(n-1) :
    check=is_co_prime(a[i],a[i+1])
    if check[0] : continue
    else :
        T=int(sqrt(check[1]))
        while True:
            if is_co_prime(a[i],T)[0] and is_co_prime(T,a[i+1])[0] :
                break
            T+=1
        insert[i]=T
        cnt+=1

for i in range(n):
    ans.append(a[i])
    if insert[i] :
        ans.append(insert[i])

print(cnt)
print(" ".join(map(str,ans)))

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    b = [a[0]]
    for i in range(1, n):
        if gcd(a[i - 1], a[i]) != 1:
            b.append(1)
        b.append(a[i])

    print(len(b) - n)
    print(" ".join(map(str, b)))


main()

n = int(input())
a = list(map(int, input().split()))
b = []

def gcd(x, y) :
    while y :
        x, y = y, x % y
    return x + y

for i in range(0, n) :
    b.append(a[i])
    if i + 1 < n and gcd(a[i], a[i + 1]) != 1 : b.append(1)

print(len(b) - n)
for x in b : print(x, end = ' ')