Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef wants to give a gift to Chefina to celebrate their anniversary. Of course, he has a sequence $a_{1}, a_{2}, \ldots, a_{N}$ ready for this occasion. Since the half-heart necklace is kind of cliche, he decided to cut his sequence into two pieces and give her a piece instead. Formally, he wants to choose an integer $l$ ($1 ≤ l < N$) and split the sequence into its prefix with length $l$ and its suffix with length $N-l$.

Chef wants his gift to be *cute*; he thinks that it will be cute if the product of the elements in Chefina's piece is coprime with the product of the elements in his piece. Can you tell him where to cut the sequence? Find the smallest valid $l$ such that Chef's gift would be cute.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains the integer $N$.
The second line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.

------  Output ------
For each test case, print a single line containing one integer $l$ where Chef should cut the sequence.

It is guaranteed that a solution exists for the given test data.

------  Constraints ------
$1 ≤ T ≤ 20$
$2 ≤ N ≤ 10^{5}$
$2 ≤ a_{i} ≤ 10^{5}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (25 points):
$N ≤ 200$
the sum of $N$ over all test cases does not exceed $600$

Subtask #2 (40 points):
$N ≤ 2,000$
the sum of $N$ over all test cases does not exceed $6,000$

Subtask #3 (35 points): original constraints

----- Sample Input 1 ------ 
1

4

2 3 4 5
----- Sample Output 1 ------ 
3

Difficulty: HARD
Tags: Number theory

Data structures

Mathematics

Range queries
Skill types: Data structures

Range queries

Starter code:

Solutions:
N = 100000
prime = [-1 for i in range(N + 1)]
i = 2
while i <= N:
	if prime[i] == -1:
		prime[i] = i
		for j in range(2 * i, N + 1, i):
			if prime[j] == -1:
				prime[j] = i
	i += 1
from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	range_p = [[-1, -1] for i in range(N + 1)]
	for i in range(n):
		a = arr[i]
		while a > 1:
			x = prime[a]
			if range_p[x][0] == -1:
				range_p[x][0] = i
				range_p[x][1] = i
			else:
				range_p[x][1] = i
			a = a // x
	mark = [0 for i in range(n)]
	for i in range(2, N + 1):
		if range_p[i][0] != -1:
			l = range_p[i][0]
			r = range_p[i][1]
			mark[l] += 1
			mark[r] -= 1
	for i in range(1, n):
		mark[i] += mark[i - 1]
	for i in range(n):
		if mark[i] == 0:
			print(i + 1)
			break


x = 10 ** 5 + 1
p = [0] * x
p[0] = p[1] = 0
for i in range(2, x):
	if not p[i]:
		for j in range(i, x, i):
			p[j] = i
t = int(input())
import random
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	e = {}
	for i in l:
		x = p[i]
		d = i
		while d > 1:
			try:
				e[x] += 1
			except:
				e[x] = 1
			d = d // x
			x = p[d]
	dp = {}
	ans = 0
	v = 1
	for i in l:
		x = p[i]
		d = i
		while d > 1:
			e[x] -= 1
			if e[x] == 0:
				ans += 1
			try:
				dp[x] += 1
			except:
				dp[x] = 1
			d = d // x
			x = p[d]
		if len(dp) == ans:
			print(v)
			break
		v += 1


import math
try:

	def primefactors(n):
		arr = []
		while n % 2 == 0:
			arr.append(2)
			n = n / 2
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				arr.append(i)
				n = n / i
		if n > 2:
			arr.append(n)
		return arr
	t = int(input())
	for _ in range(t):
		n = int(input())
		lst = list(map(int, input().split()))
		(start, ending) = ({}, {})
		for (k, i) in enumerate(lst):
			arr = primefactors(i)
			for num in arr:
				if num not in start:
					start[num] = k + 1
					ending[num] = k + 1
				else:
					ending[num] = k + 1
		diffarr = [0 for i in range(n + 1)]
		for i in start:
			diffarr[start[i]] += 1
		for i in ending:
			diffarr[ending[i]] -= 1
		for i in range(1, n):
			diffarr[i] += diffarr[i - 1]
			if diffarr[i] == 0:
				print(i)
				break
except EOFError as t:
	pass


from collections import Counter
n = 10 ** 5
fac = [[] for i in range(n + 1)]
i = 2
while i < n:
	if fac[i] == []:
		fac[i].append(i)
		j = 2 * i
		while j < n:
			fac[j].append(i)
			j += i
	i += 1
for _ in range(int(input())):
	q = int(input())
	a = list(map(int, input().split()))
	c = set()
	qw = Counter()
	for i in range(q):
		for j in fac[a[i]]:
			qw[j] += 1
			c.add(j)
	d = set()
	for i in range(q):
		for j in fac[a[i]]:
			qw[j] -= 1
			if qw[j] == 0:
				del qw[j]
				c.discard(j)
			d.add(j)
		f = 1
		for z in c:
			if z in d:
				f = 0
				break
		if f:
			print(i + 1)
			break


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict(list)
	for j in range(n):
		if a[j] % 2 == 0:
			if d.get(2) == None:
				d[2] = [j, j]
			else:
				d[2][1] = j
			while a[j] % 2 == 0:
				a[j] //= 2
		for k in range(3, int(math.sqrt(a[j])) + 1, 2):
			if a[j] % k == 0:
				if d.get(k) == None:
					d[k] = [j, j]
				else:
					d[k][1] = j
				while a[j] % k == 0:
					a[j] //= k
		if a[j] > 2:
			if d.get(a[j]) == None:
				d[a[j]] = [j, j]
			else:
				d[a[j]][1] = j
	good = [0] * n
	for j in d:
		good[d[j][0]] += 1
		good[d[j][1]] -= 1
	for j in range(n):
		if j > 0:
			good[j] += good[j - 1]
		if good[j] == 0:
			print(j + 1)
			break


from sys import stdin, stdout, maxsize
tup = lambda : map(int, stdin.readline().split())
I = lambda : int(stdin.readline())
lint = lambda : [int(x) for x in stdin.readline().split()]
stpr = lambda x: stdout.write(f'{x}' + '\n')
star = lambda x: print(' '.join(map(str, x)))
from _collections import defaultdict

def count(n):
	d = defaultdict(int)
	while n % 2 == 0:
		d[2] += 1
		n //= 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			n //= i
			d[i] += 1
	if n > 2:
		d[n] += 1
	return d
for _ in range(I()):
	n = I()
	ls = lint()
	(l, r) = (set(count(ls[0])), set())
	ans = 1
	for i in range(1, n):
		p = count(ls[i])
		r.update(p)
		if len(l.intersection(p)) > 0:
			l.update(r)
			r.clear()
			ans = i + 1
	print(ans)


import math

def primeFactors(n):
	arr = []
	while n % 2 == 0:
		arr.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			arr.append(i)
			n = n / i
	if n > 2:
		arr.append(n)
	return arr
for t in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	(st, en) = ({}, {})
	allP = set()
	for (k, i) in enumerate(lis):
		arr = primeFactors(i)
		for nums in arr:
			allP.add(nums)
			if nums not in st:
				st[nums] = k + 1
				en[nums] = k + 1
			else:
				en[nums] = k + 1
	diffarr = [0 for i in range(n + 1)]
	for i in st:
		diffarr[st[i]] += 1
	for i in en:
		diffarr[en[i]] -= 1
	for i in range(1, n):
		diffarr[i] += diffarr[i - 1]
		if diffarr[i] == 0:
			print(i)
			break


maxn = 100001
prime = [x for x in range(maxn)]
i = 2
while i * i < maxn:
	if prime[i] == i:
		j = i
		while i * j < maxn:
			if prime[i * j] == i * j:
				prime[i * j] = i
			j += 1
	i += 1
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	l = 0
	for i in range(n):
		x = a[i]
		while x > 1:
			p = prime[x]
			if p in d and d[p] <= l:
				l = i
			d[p] = i
			x //= p
	print(l + 1)


import math

def prime_factors(n):
	p = set()
	while n % 2 == 0:
		p.add(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			p.add(i)
			n = n / i
	if n > 2:
		p.add(n)
	return p
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 1
	temp = prime_factors(l[0])
	l1 = set()
	for i in range(0, n):
		fac = prime_factors(l[i])
		l1.update(fac)
		if len(temp.intersection(fac)) > 0:
			temp.update(l1)
			l1 = set()
			ans = i + 1
	print(ans)


from sys import stdin
from collections import Counter
input = stdin.readline
MAX = 10 ** 5 + 10
p = [i for i in range(MAX)]
for i in range(2, int(MAX ** 0.5) + 1):
	if p[i] == i:
		for j in range(i * i, MAX, i):
			p[j] = i
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c1 = Counter()
	for i in range(n):
		x = a[i]
		while x != 1:
			c1[p[x]] += 1
			x //= p[x]
	c2 = Counter()
	for i in range(n):
		x = a[i]
		while x != 1:
			c1[p[x]] -= 1
			c2[p[x]] += 1
			x //= p[x]
		for j in c1:
			if c1[j] > 0 and c2[j] > 0:
				break
		else:
			print(i + 1)
			break


import math as mt
MAXN = 100001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
sieve()
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	prime_factors_map = {}
	for i in range(len(arr)):
		prime_factors = getFactorization(arr[i])
		for j in prime_factors:
			if j not in prime_factors_map.keys():
				prime_factors_map[j] = {'first_index': i, 'last_index': i}
			else:
				prime_factors_map[j]['last_index'] = i
	diff_array = [0] * n
	for (key, value) in prime_factors_map.items():
		diff_array[prime_factors_map[key]['first_index']] += 1
		diff_array[prime_factors_map[key]['last_index']] -= 1
	count_array = [0] * n
	for i in range(n):
		count_array[i] = count_array[i - 1] + diff_array[i] if i - 1 >= 0 else diff_array[i]
	print(count_array.index(0) + 1)


import math as mt
from functools import lru_cache
MAXN = 100001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

@lru_cache(None)
def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
sieve()
t = int(input())
for _ in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	d = {}
	sup = {}
	al = set([])
	for i in range(0, n):
		d[i] = set(getFactorization(ls[i]))
	streak = {}
	count = -1
	for i in d:
		count += 1
		for j in d[i]:
			if j in streak:
				streak[j][1] = count
			else:
				streak[j] = [count, count]
	arr = [0] * n
	for i in streak:
		start = streak[i][0]
		end = streak[i][1]
		arr[start] += 1
		arr[end] -= 1
	prefix = arr[0]
	if prefix == 0:
		print(1)
		continue
	for i in range(1, n):
		prefix += arr[i]
		if prefix == 0:
			print(i + 1)
			break


minPrime = [0] * 100001
(minPrime[1], minPrime[2]) = (1, 2)
i = 4
while i < 100001:
	minPrime[i] = 2
	i += 2
for i in range(3, 100001, 2):
	if minPrime[i] == 0:
		minPrime[i] = i
		j = i + i
		while j < 100001:
			minPrime[j] = i
			j += i
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	dl = {}
	dr = {}
	for i in range(n - 1, -1, -1):
		j = l[i]
		while j > 1:
			try:
				dr[minPrime[j]] += 1
			except:
				dr[minPrime[j]] = 1
			j //= minPrime[j]
	for i in range(n):
		j = l[i]
		while j > 1:
			dr[minPrime[j]] -= 1
			try:
				dl[minPrime[j]] += 1
			except:
				dl[minPrime[j]] = 1
			j //= minPrime[j]
		f = True
		for k in dl:
			if dr[k]:
				f = False
				break
		if f:
			print(i + 1)
			break


from sys import stdin as stin, stdout as stout, setrecursionlimit as srl
import math as mt

def get_ints():
	return map(int, stin.readline().split())

def get_list():
	return list(map(int, stin.readline().split()))

def get_int():
	return int(stin.readline())

def get_str():
	return stin.readline()
maxm = 100001
spf = [0] * maxm

def seive():
	spf[1] = 1
	for i in range(2, maxm):
		spf[i] = i
	for i in range(4, maxm, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(maxm ** 0.5)):
		if spf[i] == i:
			for j in range(i ** 2, maxm, i):
				if spf[j] == j:
					spf[j] = i

def get_factorization(x):
	m = {}
	while x != 1:
		m[spf[x]] = 1
		x //= spf[x]
	return list(m)
seive()
for _ in range(get_int()):
	n = get_int()
	nums = get_list()
	prime = {}
	for (i, c) in enumerate(nums):
		k = get_factorization(c)
		for j in k:
			if j in prime:
				prime[j][1] = i
			else:
				prime[j] = [i, i]
	cover = [0] * n
	for i in prime:
		cover[prime[i][0]] += 1
		cover[prime[i][1]] -= 1
	if cover[0] == 0:
		print(1)
		continue
	for i in range(1, n):
		cover[i] += cover[i - 1]
		if cover[i] == 0:
			print(i + 1)
			break


import math as mt
MAXN = 100001
spf = [0 for i in range(MAXN)]
input = __import__('sys').stdin.readline

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = 1
		x = x // spf[x]
	return list(ret)

def solve(c, n):
	if c[0] == 0:
		return 1
	for i in range(1, n):
		c[i] += c[i - 1]
		if c[i] == 0:
			return i + 1
sieve()
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	prime = {}
	for i in range(n):
		q = getFactorization(a[i])
		for k in q:
			if k in prime:
				prime[k][1] = i
			else:
				prime[k] = [i, i]
	c = [0] * n
	for i in prime:
		c[prime[i][0]] += 1
		c[prime[i][1]] -= 1
	print(solve(c, n))


import math

def prime_factors(n):
	prime = set()
	while n % 2 == 0:
		prime.add(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			prime.add(i)
			n = n / i
	if n > 2:
		prime.add(n)
	return prime
for _ in range(int(input())):
	n = int(input())
	seq = list(map(int, input().split()))
	l = 1
	left = prime_factors(seq[0])
	right = set()
	for i in range(1, n):
		factors = prime_factors(seq[i])
		right.update(factors)
		if len(left.intersection(factors)) > 0:
			left.update(right)
			right = set()
			l = i + 1
	print(l)


mpr = [0 for x in range(100001)]
for i in range(2, 100001):
	if mpr[i] == 0:
		k = i
		for j in range(k, 100001, i):
			mpr[j] = i
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d1 = {}
	d2 = {}
	for i in range(n - 1, -1, -1):
		k = a[i]
		while k > 1:
			try:
				d2[mpr[k]] += 1
			except:
				d2[mpr[k]] = 1
			k = k // mpr[k]
	for i in range(n):
		k = a[i]
		while k > 1:
			d2[mpr[k]] -= 1
			try:
				d1[mpr[k]] += 1
			except:
				d1[mpr[k]] = 1
			k = k // mpr[k]
		stat = 1
		for k in d1:
			if d2[k] > 0:
				stat = 0
				break
		if stat == 1:
			print(i + 1)
			break


import sys
from math import gcd
from collections import defaultdict

def factor(a):
	factors = defaultdict(int)
	while a % 2 == 0:
		factors[2] += 1
		a //= 2
	f = 3
	while f * f <= a:
		if a % f == 0:
			factors[f] += 1
			a //= f
		else:
			f += 2
	if a != 1:
		factors[a] = 1
	return factors

def add_factors_to(fto, ffrom):
	for (k, v) in ffrom.items():
		fto[k] += v

def sub_factors_from(ffrom, ff):
	for (k, v) in ff.items():
		ffrom[k] -= v
		assert ffrom[k] >= 0
		if ffrom[k] == 0:
			del ffrom[k]

def is_coprime(a, b):
	g = 1
	if any((k in b for k in a)):
		return False
	return True

def solve(B):
	N = len(B)
	left = defaultdict(int)
	add_factors_to(left, B[0])
	right = defaultdict(int)
	for b in B[1:]:
		add_factors_to(right, b)
	split_at = 0
	while not is_coprime(left, right):
		split_at += 1
		add_factors_to(left, B[split_at])
		sub_factors_from(right, B[split_at])
	return split_at + 1

def main():
	test_cases = int(sys.stdin.readline())
	for _ in range(test_cases):
		N = int(sys.stdin.readline())
		A = [int(i) for i in sys.stdin.readline().split()]
		B = [factor(a) for a in A]
		print(solve(B))
main()


import math as mt
MAXN = 100001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
sieve()

def testcase():
	n = int(input())
	arr = list(map(int, input().split()))
	if n > 1000:
		first = dict()
		last = dict()
		for i in range(n):
			fs = getFactorization(arr[i])
			for f in fs:
				if f not in first:
					first[f] = i + 1
				last[f] = i + 1
		fs = getFactorization(arr[0])
		ans = 0
		for f in fs:
			ans = max(ans, last[f])
		for f in first:
			if first[f] < ans:
				ans = max(ans, last[f])
		print(ans)
		return
	ls = [0 for a in arr]
	ls[0] = set(getFactorization(arr[0]))
	for i in range(1, n):
		fs = getFactorization(arr[i])
		fs = set(fs)
		ls[i] = set(ls[i - 1])
		ls[i] |= fs
	rs = [0 for a in arr]
	rs[-1] = set(getFactorization(arr[-1]))
	for i in range(n - 2, -1, -1):
		fs = getFactorization(arr[i])
		fs = set(fs)
		rs[i] = set(rs[i + 1])
		rs[i] |= fs
	for i in range(n - 1):
		l = ls[i]
		r = rs[i + 1]
		if len(l & r) == 0:
			print(i + 1)
			return
	return
import sys, os
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
sys.setrecursionlimit(10 ** 5)
t = int(input())
for _ in range(t):
	testcase()


import sys
import math
import collections
from sys import stdin, stdout, setrecursionlimit
import bisect as bs
setrecursionlimit(2 ** 20)
M = 10 ** 9 + 7
T = int(stdin.readline())

def primeFactors(n):
	h = {}
	while n % 2 == 0:
		if 2 not in h:
			h[2] = 0
		h[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i not in h:
				h[i] = 0
			h[i] += 1
			n = n / i
	if n > 2:
		if n not in h:
			h[n] = 1
		h[n] += 1
	return h
for _ in range(T):
	f = {}
	fac = []
	b = {}
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	for i in range(n):
		d = primeFactors(a[i])
		for k in d:
			if k not in f:
				f[k] = 0
			f[k] += d[k]
		fac.append(d)
	for i in range(n):
		res = True
		d = fac[i]
		for k in d:
			if k not in b:
				b[k] = 0
			b[k] += d[k]
			f[k] -= d[k]
		for k in b:
			if f[k] != 0:
				res = False
				break
		if res:
			print(i + 1)
			break


n = 10 ** 5 + 5
seive = [0 for i in range(n)]
for i in range(2, n):
	if seive[i] == 0:
		seive[i] = i
		for j in range(i * i, n, i):
			seive[j] = i
t = int(input())
for you in range(t):
	n = int(input())
	l = input().split()
	li = [int(i) for i in l]
	hashi = dict()
	for i in li:
		z = i
		while z > 1:
			if seive[z] in hashi:
				hashi[seive[z]] += 1
			else:
				hashi[seive[z]] = 1
			z = z // seive[z]
	start = dict()
	k = len(hashi)
	for i in range(n):
		z = li[i]
		while z > 1:
			hashi[seive[z]] -= 1
			start[seive[z]] = 1
			if hashi[seive[z]] == 0:
				del hashi[seive[z]]
			z = z // seive[z]
		if len(hashi) + len(start) == k:
			ans = i
			break
	print(ans + 1)