You're given an array A of N integers. You need to find the minimum cost of creating another array B of N integers with the following properties

B_{i} ≥ 0 for each 1 ≤ i ≤ N
The GCD of adjacent elements of B is equal to 1, i.e, \gcd(B_{i}, B_{i+1}) = 1 for each 1 ≤ i < N

The cost of creating B is defined as follows:

\sum_{i=1}^{N} 2^{|A_{i} - B_{i} |}

Find the minimum possible cost to create the array B. Since the answer can be huge print it modulo 10^{9}+7

Note: You need to minimize the value of total cost of creating the array B, and then print this minimum value modulo 10^{9} + 7. For example, suppose there is a way to create the required B with a cost of 500, and another way to do it with a cost of 10^{9} + 7 (which is 0 \pmod {10^{9} + 7}). The output in this case would be 500 and not 0.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first line of each test case contains an integer N - the length of the array A
- The second line of each test case contains N space-separated integers A_{1},A_{2},\ldots,A_{N}

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

For each test case, output on a new line the minimum cost of creating the array B, modulo 10^{9} + 7.

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

$1 ≤ T ≤ 150$
$1 ≤ N ≤ 10^{4}$
$1 ≤ A_{i} ≤ 10^{6}$
- The sum of $N$ over all test cases won't exceed $10^{4}$.

----- Sample Input 1 ------ 
3
3
15 16 19
2
5 10
7
9 15 7 19 10 7 1

----- Sample Output 1 ------ 
3
3
8
----- explanation 1 ------ 
Test case $1$: The given input already satisfies all the conditions, hence we can take $B = A$ with a cost of $2^{0} + 2^{0} + 2^{0} = 3$.

Test case $2$: One optimal way is to choose $B$ as $ [ 5, 11 ] $, with a cost of $2^{0} + 2^{1} = 3$.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Mathematics


Solutions:
from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		arr = lis()
		dp = [[inf] * 21 for i in range(n)]
		for i in range(-10, 11):
			dp[0][i] = 1 << abs(i)
		for i in range(1, n):
			for j in range(-10, 11):
				for k in range(-10, 11):
					if math.gcd(arr[i - 1] + j, arr[i] + k) == 1:
						dp[i][k] = min(dp[i][k], dp[i - 1][j] + (1 << abs(k))) % M
		ans = inf
		for i in range(-10, 11):
			ans = min(ans, dp[n - 1][i])
		print(ans % M)
main()


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

def solve(N, A):
	k = 10
	dp = [None] * N
	dp[0] = {j: 2 ** abs(j) for j in range(-k, k + 1)}
	for i in range(1, N):
		dp[i] = {j: float('inf') for j in range(-k, k + 1)}
		for j1 in range(-k, k + 1):
			cost = 2 ** abs(j1)
			for j2 in range(-k, k + 1):
				if gcd(A[i - 1] + j2, A[i] + j1) == 1:
					dp[i][j1] = min(dp[i][j1], dp[i - 1][j2] + cost)
	return min((dp[N - 1][j] for j in range(-k, k + 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()]
	print(solve(N, A))


import sys, math
input = sys.stdin.readline
M = int(1000000000.0) + 7
k = 5

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	dp = [[float('inf') for _ in range(2 * k + 1)] for _ in range(n)]
	for j in range(-k, k + 1):
		dp[0][j + k] = 2 ** abs(j)
	for i in range(1, n):
		for j in range(-k, k + 1):
			for jj in range(-k, k + 1):
				(x, y) = (a[i] + j, a[i - 1] + jj)
				if x < 0 or y < 0:
					continue
				if math.gcd(x, y) > 1:
					continue
				if dp[i - 1][jj + k] == float('inf'):
					continue
				dp[i][j + k] = min(dp[i][j + k], dp[i - 1][jj + k] + 2 ** abs(j))
	return min(dp[-1]) % M
for _ in range(int(input())):
	print(solve())


import sys
sys.setrecursionlimit(1000000)

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())

def yn(ans):
	if ans:
		print('YES')
	else:
		print('NO')
from math import gcd
for T in range(int(input())):
	n = ni()
	a = li()
	dp = []
	k = 3
	from math import inf
	for i in range(2 * k + 1):
		dp.append([inf] * n)
	for i in range(2 * k + 1):
		dp[i][0] = 2 ** abs(i - k)
	for i in range(1, n):
		for j in range(2 * k + 1):
			for l in range(2 * k + 1):
				if gcd(a[i] + (j - k), a[i - 1] + l - k) == 1:
					dp[j][i] = min(dp[j][i], dp[l][i - 1] + 2 ** abs(j - k))
	ans = inf
	for i in dp:
		ans = min(i[-1], ans)
	print(ans)