Chef considers an array *good* if it has no subarray of size less than N such that the [GCD] of all the elements of the subarray is equal to 1. 

Chef has an array A of size N with him. He wants to convert it into a *good* array by applying a specific operation.  
In one operation, Chef can choose any subarray and reverse it.

Find the minimum number of operations required to convert the array into a *good* array and the operations themselves. If there are multiple ways to achieve the result, print any.  
If it is not possible to convert the array into a *good* array, print -1 instead.

Note: A subarray of an array is formed by deletion of several (possibly zero) elements from the beginning and several (possibly zero) elements from the end of the array.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- The first line of each test case contains of single integer N denoting the length of the array.
- The second line contains N space-separated integers A_{1}, A_{2},\ldots, A_{N} representing the initial array.

------ Output Format ------ 

- If there is a way to convert the given array into a *good* array, then:
- In a single line, output X denoting the minimum number of operations required.
- In the following X lines, output 2 integers - L and R denoting the left and right index of the subarray you want to reverse. Note that, (1≤ L≤ R≤ N).
- If there is no way to convert, print -1 in a single line. 

------ Constraints ------ 

$1 ≤ T ≤ 4000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{18}$
- The sum of $N$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
3
3
3 2 6
4
3 2 4 8
4
6 15 9 18
 
----- Sample Output 1 ------ 
1
2 3
-1
0

----- explanation 1 ------ 
Test case $1$: We need only one operation to convert the array into a *good* array. Choose $L = 2, R = 3$ and reverse the subarray $[2, 6]$ to $[6, 2]$. Thus, the final array is $[3, 6, 2]$. Note that in the final array, no subarray of length less than $N$ has *gcd* equal to $1$.

Test case $2$: It is not possible to convert the given array to a *good* array using any number of operations.

Test case $3$: The given array is already *good*. That is, no subarray of length less than $N$ has *gcd* equal to $1$. Thus, we need $0$ operations.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Mathematics


Solutions:
def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	flag = 0
	cur = A[0]
	for i in range(1, n):
		new = gcd(cur, A[i])
		if new == 1:
			if flag == 0:
				flag = 1
				r = i
				continue
			print(-1)
			break
		cur = new
	else:
		if flag == 0:
			print(0)
			continue
		(A[r], A[-1]) = (A[-1], A[r])
		flag = 0
		cur = A[-1]
		l = 0
		for i in range(n - 2, -1, -1):
			g = gcd(A[i], cur)
			if g == 1:
				if flag == 0:
					flag = 1
					l = i
					continue
				print(-1)
				break
			cur = g
		else:
			if l == 0 and r == n - 1:
				print(0)
				continue
			if l == 0:
				print(1)
				print(r + 1, n)
				continue
			if r == n - 1:
				print(1)
				print(1, l + 1)
				continue
			print(2)
			print(1, l + 1)
			print(r + 1, n)


import math

def gcdd(n, l):
	p = [0] * (n + 2)
	s = [0] * (n + 2)
	for i in range(n):
		p[i + 1] = math.gcd(p[i], l[i])
	for i in range(n - 1, -1, -1):
		s[i + 1] = math.gcd(s[i + 2], l[i])
	if p[-2] != 1:
		print(0)
		return
	indx = []
	for i in range(1, n + 1):
		if math.gcd(p[i - 1], s[i + 1]) != 1:
			indx.append(i)
	if len(indx) < 2:
		print(-1)
		return
	a = []
	if indx[0] != 1:
		a.append((1, indx[0]))
	if indx[-1] != n:
		a.append((indx[-1], n))
	print(len(a))
	for j in a:
		print(*j)
t = int(input())
while t > 0:
	n = int(input())
	ar = list(map(int, input().split()))
	gcdd(n, ar)
	t -= 1


import math

def ga(n, l):
	pgcd = [0] * (n + 2)
	sgcd = [0] * (n + 2)
	for i in range(n):
		pgcd[i + 1] = math.gcd(pgcd[i], l[i])
	for i in range(n - 1, -1, -1):
		sgcd[i + 1] = math.gcd(sgcd[i + 2], l[i])
	if pgcd[-2] != 1:
		print(0)
		return
	ind = []
	for i in range(1, n + 1):
		if math.gcd(pgcd[i - 1], sgcd[i + 1]) != 1:
			ind.append(i)
	if len(ind) < 2:
		print(-1)
		return
	ans = []
	if ind[0] != 1:
		ans.append((1, ind[0]))
	if ind[-1] != n:
		ans.append((ind[-1], n))
	print(len(ans))
	for i in ans:
		print(*i)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ga(n, arr)


import collections
import heapq
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os

def values():
	return tuple(map(int, sys.stdin.readline().split()))

def inlsts():
	return [int(i) for i in sys.stdin.readline().split()]

def inp():
	return int(sys.stdin.readline())

def instr():
	return sys.stdin.readline().strip()

def words():
	return [i for i in sys.stdin.readline().strip().split()]

def chars():
	return [i for i in sys.stdin.readline().strip()]

def solve():
	n = inp()
	l = inlsts()
	pgcd = [0] * (n + 2)
	sgcd = [0] * (n + 2)
	for i in range(n):
		pgcd[i + 1] = math.gcd(pgcd[i], l[i])
	for i in range(n - 1, -1, -1):
		sgcd[i + 1] = math.gcd(sgcd[i + 2], l[i])
	if pgcd[-2] != 1:
		print(0)
		return
	ind = []
	for i in range(1, n + 1):
		if math.gcd(pgcd[i - 1], sgcd[i + 1]) != 1:
			ind.append(i)
	if len(ind) < 2:
		print(-1)
		return
	ans = []
	if ind[0] != 1:
		ans.append((1, ind[0]))
	if ind[-1] != n:
		ans.append((ind[-1], n))
	print(len(ans))
	for i in ans:
		print(*i)
for i in range(inp()):
	solve()


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	pgcd = [0 for i in range(n)]
	sgcd = [0 for i in range(n)]
	pgcd[0] = l[0]
	for i in range(1, n):
		pgcd[i] = gcd(pgcd[i - 1], l[i])
	sgcd[-1] = l[-1]
	for i in range(n - 2, -1, -1):
		sgcd[i] = gcd(sgcd[i + 1], l[i])
	if pgcd[-1] != 1:
		print(0)
		continue
	count = 0
	ind = []
	for i in range(n):
		if i == 0:
			g = sgcd[i + 1]
		elif i == n - 1:
			g = pgcd[i - 1]
		else:
			g = gcd(pgcd[i - 1], sgcd[i + 1])
		if g != 1:
			count += 1
			ind.append(i)
	if count < 2:
		print(-1)
	elif 0 in ind and n - 1 in ind:
		print(0)
	elif 0 in ind:
		print(1)
		print(1 + ind[1], n)
	elif n - 1 in ind:
		print(1)
		print(1, ind[0] + 1)
	else:
		print(2)
		print(1, 1 + ind[0])
		print(1 + ind[1], n)


import sys, math

def get_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(sys.stdin.readline())
for t2 in range(t):
	n = int(sys.stdin.readline())
	a = get_arr()
	if n == 2:
		print(0)
		continue
	arr = a
	num1 = a[0]
	num2 = a[1]
	gcd = find_gcd(num1, num2)
	idx1 = -1
	idx2 = -1
	if gcd == 1:
		idx1 = 1
	else:
		for i in range(2, n):
			gcd = find_gcd(gcd, a[i])
			if gcd == 1:
				idx1 = i
				break
	if idx1 == -1:
		print(0)
		continue
	swaps = 0
	ans = []
	if idx1 != n - 1:
		temp = arr[-1]
		arr[-1] = arr[idx1]
		arr[idx1] = temp
		swaps += 1
		ans.append([idx1 + 1, n])
	num1 = a[0]
	num2 = a[1]
	gcd = find_gcd(num1, num2)
	fl = 0
	for i in range(2, n - 1):
		if gcd == 1:
			print(-1)
			fl = 1
			break
		gcd = find_gcd(gcd, a[i])
	if gcd == 1 and fl != 1:
		print(-1)
		fl = 1
	if fl == 1:
		continue
	a.reverse()
	num1 = a[0]
	num2 = a[1]
	gcd = find_gcd(num1, num2)
	idx1 = -1
	idx2 = -1
	if gcd == 1:
		idx1 = 1
	else:
		for i in range(2, n - 1):
			gcd = find_gcd(gcd, a[i])
			if gcd == 1:
				idx1 = i
				break
	if idx1 == -1:
		print(swaps)
		for i in ans:
			print(*i)
		continue
	temp = arr[-1]
	arr[-1] = arr[idx1]
	arr[idx1] = temp
	swaps += 1
	ans.append([1, n - idx1])
	num1 = a[0]
	num2 = a[1]
	gcd = find_gcd(num1, num2)
	fl = 0
	for i in range(2, n - 1):
		if gcd == 1:
			print(-1)
			fl = 1
			break
		gcd = find_gcd(gcd, a[i])
	if gcd == 1 and fl != 1:
		print(-1)
		fl = 1
	if fl == 1:
		continue
	print(swaps)
	for i in ans:
		print(*i)


from math import gcd
from sys import stdin
input = stdin.readline

def good(N, A):
	G = A[0]
	for i in range(1, N - 1):
		G = gcd(A[i], G)
		if G == 1:
			return False
	G = A[1]
	for i in range(2, N):
		G = gcd(A[i], G)
		if G == 1:
			return False
	return True

def solve(N, A):
	if N == 2:
		if gcd(*A) == 1:
			return (0, [])
		else:
			return (-1, [])
	G = A[0]
	k = None
	for i in range(1, N):
		G = gcd(A[i], G)
		if G == 1:
			k = i
			break
	if k == None:
		return (0, [])
	count = 0
	operations = []
	if k != N - 1:
		count += 1
		operations.append((k + 1, N))
		A = A[:k] + list(reversed(A[k:]))
	G = A[N - 1]
	k = None
	for i in reversed(range(N - 1)):
		G = gcd(A[i], G)
		if G == 1:
			k = i
			break
	if k != None and k != 0:
		count += 1
		operations.append((1, k + 1))
		A = list(reversed(A[:k + 1])) + A[k + 1:]
	if good(N, A):
		return (count, operations)
	else:
		return (-1, [])
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()]
	(X, operations) = solve(N, A)
	print(X)
	for operation in operations:
		print(*operation)