You have an array a[1], a[2], ..., a[n], containing distinct integers from 1 to n. Your task is to sort this array in increasing order with the following operation (you may need to apply it multiple times):

  choose two indexes, i and j (1 ≤ i < j ≤ n; (j - i + 1) is a prime number);  swap the elements on positions i and j; in other words, you are allowed to apply the following sequence of assignments: tmp = a[i], a[i] = a[j], a[j] = tmp (tmp is a temporary variable). 

You do not need to minimize the number of used operations. However, you need to make sure that there are at most 5n operations.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The next line contains n distinct integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).


-----Output-----

In the first line, print integer k (0 ≤ k ≤ 5n) — the number of used operations. Next, print the operations. Each operation must be printed as "i j" (1 ≤ i < j ≤ n; (j - i + 1) is a prime).

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


-----Examples-----
Input
3
3 2 1

Output
1
1 3

Input
2
1 2

Output
0

Input
4
4 2 3 1

Output
3
2 4
1 2
2 4

Difficulty: interview

Starter code:

Solutions:
import bisect


def gen_primes(upper_bound):
    upper_bound += 1
    t = [0] * (upper_bound)
    primes = [2]
    for i in range(3, upper_bound, 2):
        if t[i]:
            continue
        primes.append(i)
        for j in range(i + i, upper_bound, i):
            t[j] = 1
    return primes

def main():
    n = int(input())
    a = list(map(int, input().split()))
    primes = gen_primes(n + 1)
    process = list()
    d = [0] * n

    for i in range(n):
        d[a[i] - 1] = i

    i = 0
    while i < n:
        if a[i] == i + 1:
            i += 1
            continue
        r = d[i]
        l = r - primes[bisect.bisect(primes, r - i + 1) - 1] + 1
        a[l], a[r] = a[r], a[l]
        process.append('{} {}'.format(l + 1, r + 1))
        d[a[l] - 1] = l
        d[a[r] - 1] = r

    print(len(process))
    print('\n'.join(process))

def __starting_point():
    main()

__starting_point()

def prime(n):
    n += 1
    p = [False] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        u, v = i * i, 2 * i
        if not p[i]: p[u :: v] = [True] * ((n - u - 1) // v + 1)
    p[4 :: 2] = [True] * ((n - 3) // 2)
    return p
n = int(input())
t = list(enumerate(list(map(int, input().split())), 1))
t.sort(key = lambda x: x[1])
t = [x[0] for x in t]
u, v, q = list(range(n + 1)), list(range(n + 1)), []
p = prime(n + 1)
for i, j in enumerate(t, 1):
    while i != u[j]:
        k = i
        while p[u[j] - k + 1]: k += 1
        q.append(str(k) + ' ' + str(u[j]))
        a, b = u[j], v[k]
        u[b], u[j], v[a], v[k] = a, k, b, j
print(len(q))
print('\n'.join(q))

from sys import stdin
_data = iter(stdin.read().split('\n'))
input = lambda: next(_data)

from bisect import bisect
V = 210000
primes = []
is_prime = [True] * V
is_prime[0] = False
is_prime[1] = False
for i in range(2, V):
    if is_prime[i]:
        primes.append(i)
        for j in range(i + i, V, i):
            is_prime[j] = False

n = int(input())
a = list(map(int, input().split()))
ra = [0] * n
for i in range(n):
    a[i] -= 1
    ra[a[i]] = i

buf = []
p = 0
while p < n:
    while ra[p] != p:
        d = ra[p] - p + 1
        d = primes[bisect(primes, d) - 1] - 1
        r = ra[p]
        q = r - d
        ra[a[q]], ra[a[r]] = ra[a[r]], ra[a[q]]
        a[q], a[r] = a[r], a[q]
        buf.append('{} {}'.format(q + 1, r + 1))
    p += 1
print(len(buf))
print('\n'.join(buf))


import bisect





def gen_primes(upper_bound):

    upper_bound += 1

    t = [0] * (upper_bound)

    primes = [2]

    for i in range(3, upper_bound, 2):

        if t[i]:

            continue

        primes.append(i)

        for j in range(i + i, upper_bound, i):

            t[j] = 1

    return primes



def main():

    n = int(input())

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

    primes = gen_primes(n + 1)

    process = list()

    d = [0] * n



    for i in range(n):

        d[a[i] - 1] = i



    i = 0

    while i < n:

        if a[i] == i + 1:

            i += 1

            continue

        r = d[i]

        l = r - primes[bisect.bisect(primes, r - i + 1) - 1] + 1

        a[l], a[r] = a[r], a[l]

        process.append('{} {}'.format(l + 1, r + 1))

        d[a[l] - 1] = l

        d[a[r] - 1] = r



    print(len(process))

    print('\n'.join(process))



def __starting_point():

    main()





# Made By Mostafa_Khaled

__starting_point()

def sieve(n): 
    p = 2
    while (p * p <= n): 
        if (prime[p] == False): 
            for i in range(p * p, n+1, p): 
                prime[i] = True
        p += 1
n = int(input())
prime = [False for i in range(n+2)] 
prime[0]=1
prime[1]=1
sieve(n+1)
lis = [0]+list(map(int,input().split()))
ind=[0]*(n+1)
ct=0
for i in range(1,n+1):
    ind[lis[i]]=i
#print(prime,ind)
ans=[]
for i in range(1,n+1):
    j=ind[i]
    while j>i:
        t=i
        while prime[j-t+1]:
            t+=1
#        print(j,t)
        ct+=1
        ind[lis[j]]=t;ind[lis[t]]=j
        ans.append([t,j])
        lis[j],lis[t]=lis[t],lis[j] 
        j=t
print(ct)
for i in ans:
    print(*i)           




def sieve(n): 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
n = int(input())
prime = [True for i in range(n+2)] 
prime[0]=0
prime[1]=0
sieve(n+1)
aa=[0]*(n+1)
for i in range(n+1):
    if prime[i]:
        aa[i]=i
    else:
        aa[i]=aa[i-1]    
lis = [0]+list(map(int,input().split()))
ind=[0]*(n+1)
ct=0
for i in range(1,n+1):
    ind[lis[i]]=i
ans=[]
for i in range(1,n+1):
    j=ind[i]
    while j>i:
        t=i
        step=aa[j-t+1]-1    
        ct+=1
        ind[lis[j-step]]=j;ind[lis[j]]=j-step
        ans.append([j-step,j])
        lis[j-step],lis[j]=lis[j],lis[j-step]
        j-=step
print(ct)
for i in ans:
    print(*i)           


import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))

n,=I()
l=I()
an=[]
sv=[0]*(10**5+10)
for i in range(2,len(sv)):
	if not sv[i]:
		sv[i]=i
		for j in range(2*i,len(sv),i):
			sv[j]=1
sv[0]=sv[1]=1
for i in range(2,len(sv)):
	if not sv[i]-1:
		sv[i]=sv[i-1]
ix=[0]*(n+1)
for i in range(n):
	ix[l[i]]=i
for i in range(n):
	ct=0
	while l[i]!=i+1 and ct<5:
		cr=ix[i+1]
		pr=sv[cr-i+1]
		#print(i,cr,pr)
		an.append(sorted([cr+1,cr-pr+2]))
		l[cr],l[cr-pr+1]=l[cr-pr+1],l[cr]
		ix[l[cr]],ix[l[cr-pr+1]]=ix[l[cr-pr+1]],ix[l[cr]]
		ct+=1
print(len(an))
for i in an:
	print(*i)

import sys
import collections as cc
import bisect as bi
input=sys.stdin.readline
I=lambda:list(map(int,input().split()))
pr=[]
N=10**6+3
ss=[0]*(N)
ss[0]=1
for i in range(2,N):
	if ss[i]==0:
		ss[i]=i
		pr.append(i)
		for j in range(2*i,N,i):
			ss[j]=i
n,=I()
l=I()
f={}
ans=0
an=[]
for i in range(n):
	f[l[i]]=i
for i in range(n):
	while l[i]!=i+1	:
		ans+=1
		now=f[i+1]
		dis=now-i+1
		temp=bi.bisect(pr,dis)
		temp=pr[temp-1]
		#print(l[i],i+1,temp)
		f[l[now]],f[l[now-temp+1]]=f[l[now-temp+1]],f[l[now]]
		l[now-temp+1],l[now]=l[now],l[now-temp+1]
		an.append([now+1,now-temp+2])
print(ans)
for i in an:
	print(*i[::-1])



import sys
input = sys.stdin.readline
import bisect

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

for i in range(n):
    A[i]-=1

x=10**5
import math 
L=math.floor(math.sqrt(x)) # 平方根を求める

Primelist=[i for i in range(x+1)]
Primelist[1]=0 # 1は素数でないので0にする.
 
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0

Primes=[Primelist[j]-1 for j in range(x+1) if Primelist[j]!=0]

A_INV=[-1]*n
for i in range(n):
    A_INV[A[i]]=i

ANS=[]
for i in range(n):

    j=A_INV[i]

    while j-i:
        t=bisect.bisect(Primes,j-i)-1
        sa=Primes[t]

        ANS.append((j-sa,j))

        A_INV[i],A_INV[A[j-sa]]=j-sa,j
        A[j],A[j-sa]=A[j-sa],A[j]

        j-=sa
        
print(len(ANS))
for x,y in ANS:
    print(x+1,y+1)