Given an array of N elements, find the minimum number of insertions to convert the given array into a co-prime array adjacent pair-wise. 
Example 1:
Input: A[] = {2, 7, 28}
Output: 1
Explanation: Here, 1st pair = {2, 7}
are co-primes( gcd(2, 7) = 1). 2nd pair
= {7, 28} are not co-primes, insert 9
between them. gcd(7, 9) = 1 and
gcd(9, 28) = 1.
Example 2:
Input: A[] = {5, 10, 20}
Output : 2
Explanation: Here, there is no pair
which are co-primes. Insert 7 between
(5, 10) and 1 between (10, 20).
Your Task:
The input is already taken care of by the driver code. You only need to complete the function countCoPrime() that takes an array (arr), sizeOfArray (n), and return the minimum number of insertions. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1<=N<=10^{5}
1<=arr<=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3
class Solution:
	def countCoPrime (self,arr,  n):
		#Complete the function


Solutions:
from fractions import gcd

class Solution:

	def countCoPrime(self, arr, n):

		def gcd(m, n):
			while n:
				(m, n) = (n, m % n)
			return abs(m)
		c = 0
		for i in range(0, n - 1, 1):
			if gcd(arr[i], arr[i + 1]) != 1:
				c += 1
		return c


import math

class Solution:

	def countCoPrime(self, arr, n):
		count = 0
		for i in range(n - 1):
			if math.gcd(arr[i], arr[i + 1]) != 1:
				count += 1
		return count


class Solution:

	def countCoPrime(self, arr, n):
		count = 0
		for index in range(n - 1):
			m = max(arr[index + 1], arr[index])
			mi = min(arr[index + 1], arr[index])
			if not self.isGcd(m, mi):
				count += 1
		return count

	def isGcd(self, p, q):
		while q != 0:
			(p, q) = (q, p % q)
		return p == 1


import math as m

class Solution:

	def countCoPrime(self, arr, n):
		c = 0
		for i in range(n - 1):
			if m.gcd(arr[i], arr[i + 1]) != 1:
				c = c + 1
		return c


class Solution:

	@staticmethod
	def gcd(a, b):
		if b == 0:
			return a
		else:
			return Solution.gcd(b, a % b)

	def countCoPrime(self, arr, n):
		count = 0
		for i in range(1, n, 1):
			if Solution.gcd(arr[i], arr[i - 1]) != 1:
				count += 1
		return count


from math import gcd

class Solution:

	def countCoPrime(self, arr, n):
		c = 0
		for k in range(n - 1):
			a = min(arr[k], arr[k + 1])
			b = max(arr[k], arr[k + 1])
			r = b % a
			if gcd(a, b) != 1:
				c += 1
		return c


class Solution:

	def countCoPrime(self, arr, n):

		def notCoprime(x, y):
			if x < 2 or y < 2:
				return 0
			rem = x % y
			x = y
			y = rem
			while y != 0:
				rem = x % y
				x = y
				y = rem
			if x == 1:
				return 0
			else:
				return 1
		ans = 0
		for i in range(n - 1):
			ans += notCoprime(arr[i], arr[i + 1])
		return ans


import math

class Solution:

	def countCoPrime(self, arr, n):
		res = 0
		for i in range(n - 1):
			if math.gcd(arr[i], arr[i + 1]) == 1:
				pass
			else:
				res += 1
		return res


class Solution:

	def countCoPrime(self, arr, n):

		def isNotCoPrime(x, y):
			if x < 2 or y < 2:
				return 0
			temp = x % y
			x = y
			y = temp
			while y != 0:
				temp = x % y
				x = y
				y = temp
			return 0 if x == 1 else 1
		res = 0
		for i in range(len(arr) - 1):
			res += isNotCoPrime(arr[i], arr[i + 1])
		return res


class Solution:

	def countCoPrime(self, arr, n):

		def gcd(a, b):
			if a == 0:
				return b
			return gcd(b % a, a)
		c = 0
		for i in range(n - 1):
			if gcd(arr[i], arr[i + 1]) != 1:
				c = c + 1
		return c


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

class Solution:

	def countCoPrime(self, arr, n):
		count = 0
		for x in range(n - 1):
			if gcd(arr[x], arr[x + 1]) != 1:
				count += 1
		return count


from math import gcd

class Solution:
	from math import gcd

	def countCoPrime(self, arr, n):
		count = 0
		for i in range(len(arr) - 1):
			if gcd(arr[i], arr[i + 1]) != 1:
				count = count + 1
			else:
				continue
		return count


class Solution:

	def isgcd(self, num1, num2):
		if num1 == 0:
			return num2
		return self.isgcd(num2 % num1, num1)

	def countCoPrime(self, arr, n):
		count = 0
		for i in range(n - 1):
			if self.isgcd(arr[i], arr[i + 1]) != 1:
				count += 1
		return count


from fractions import gcd

class Solution:

	def countCoPrime(self, arr, n):
		count = 0
		for i in range(1, n):
			if gcd(arr[i], arr[i - 1]) != 1:
				count += 1
		return count
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.countCoPrime(arr, n)
	print(res)


class Solution:

	def countCoPrime(self, arr, n):
		import math
		c = 0
		for i in range(0, n - 1):
			if math.gcd(arr[i], arr[i + 1]) != 1:
				c += 1
		return c
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.countCoPrime(arr, n)
	print(res)


class Solution:

	def countCoPrime(self, arr, n):
		count = 0
		for i in range(n - 1):
			if self.gcd(arr[i], arr[i + 1]) != 1:
				count += 1
		return count

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


from fractions import gcd

class Solution:

	def countCoPrime(self, arr, n):
		c = 0
		for i in range(len(arr) - 1):
			if gcd(arr[i], arr[i + 1]) != 1:
				c += 1
		return c


from fractions import gcd

class Solution:

	def countCoPrime(self, arr, n):
		count = 0
		for i in range(1, n):
			if gcd(arr[i], arr[i - 1]) != 1:
				count += 1
		for i in range(1, n):
			if gcd(arr[i], arr[i - 1]) != 1:
				pass
		return count