You are given a sequence of integers $A_1, A_2, \ldots, A_N$. This sequence is circular ― for each valid $i$, the element $A_{i+1}$ follows after $A_i$, and the element $A_1$ follows after $A_N$.
You may insert any positive integers at any positions you choose in this sequence; let's denote the resulting sequence by $B$. This sequence is also circular. For each pair of its elements $B_s$ and $B_f$, let's denote the (non-circular) sequence created by starting at $B_s$ and moving from each element to the one that follows after it, until we reach $B_f$, by $B(s, f)$. This sequence includes the elements $B_s$ and $B_f$.
For each $K$ from $2$ to $N$ inclusive, find the smallest possible number of elements that need to be inserted into $A$ to form a sequence $B$ for which there is no subsequence $B(p, q)$ such that:
- The size of $B(p, q)$ is at least $K$.
- There is no pair of consecutive elements in $B(p, q)$ such that their GCD is equal to $1$.

-----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 a single 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 $N-1$ space-separated integers. For each $i$ ($1 \le i \le N-1$), the $i$-th of these integers should be the smallest number of inserted elements in a valid sequence $B$ for $K = i+1$.

-----Constraints-----
- $1 \le T \le 2,000$
- $2 \le N \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^6$

-----Example Input-----
1
5
3 6 4 5 9

-----Example Output-----
3 1 1 0

Difficulty: interview

Starter code:

Solutions:
from math import gcd
from itertools import groupby

def gcd_split(seq):
 gcds= [int(gcd(a,b)==1) for a,b in zip(seq[1:],seq[:-1])]
 gcds.append(int(gcd(seq[0],seq[-1])==1))
 # print(gcds)
 if max(gcds)==0:
  return -1
 else:
  splits=[len(list(x))+1 for num,x in groupby(gcds) if num==0]
  # print(splits)
  if gcds[0]==gcds[-1]==0:
   splits[0] += splits[-1]-1
   splits = splits[:-1]
  return splits

for _ in range(int(input())):
 N=int(input())
 A=[int(x) for x in input().split()]
 split = gcd_split(A)
 # print(split)
 
 res=[]
 if split!=-1:
  for K in range(2,N+1):
   temp=(x for x in split if x>=K)
   ins = sum([(x//(K-1)-1 if x%(K-1)==0 else x//(K-1)) for x in temp])
   if ins==0:
    break
   else:
    res.append(ins)
 else:
  for K in range(2,N+1):
   ins = N//(K-1)+(N%(K-1)>0)
   if ins==0:
    break
   else:
    res.append(ins)
 
 res = res + [0]*(N-1 -len(res))
 print(*res)

# cook your dish here
def gcd(m,n):
 if m > n :
  (a,b) = (n,m)
 else:
  (a,b) = (m,n)
 r = b
 while r > 1:
  r = b%a 
  (a,b) = (r,a)
 if r == 0:
  return b
 else:
  return 1

def rlmaker(rl,pc,n):
 d = 1 
 for i in range(0,pc+1):
  if i <n-1 :
   rl[i] += pc//d
   d+=1
 return rl
def rlmakers(rl,pc,n):
 d = 1 
 for i in range(0,pc+1):
  if i <n-1 :
   if pc%d == 0:
    rl[i] += pc//d
   else:
    rl[i] += ((pc//d)+1)
   d+=1
 return rl
  
  
def insFinder(n,l):
 lstone = 0
 rl = []
 for i in range(0,n-1):
  rl.append(0)
 pathli = []
 pc = 0
 start = -1
 end = -1
 c = 0
 for i in range (0,n-1):
  if gcd(l[i],l[i+1]) != 1 :
   if i == 0:
    start = 0
   if i == n-2:
    end = n-1
   if lstone == 1:
    pc += 1 
   else:
    lstone = 1 
    pc += 1
  else:
   if lstone == 1:
    pathli.append(pc)
    pc = 0
    lstone = 0
    
 if start == 0:
  if end == n-1:
   if gcd(l[n-1],l[0]) != 1:
    pathli.append(pc)
    if len(pathli) > 1:
     pathli[0]+= (pathli[len(pathli)-1]+1)
     pathli.remove(pathli[len(pathli)-1])
    else:
     c = 1
     pathli[0]+=1
   else:
    pathli.append(pc)
  else:
   if gcd(l[n-1],l[0]) != 1:
    pathli[0] += 1
 else:
  if end == n-1:
   if gcd(l[n-1],l[0]) != 1:
    pc += 1
    pathli.append(pc)
   else:
    pathli.append(pc)
  else:
   if gcd(l[n-1],l[0]) != 1:
    pathli.append(1) 
 if c == 1:
  rl = rlmakers(rl,pathli[0],n)
 else:
  for i in range(0,len(pathli)):
   rl = rlmaker(rl,pathli[i],n)
 
 for i in range(0,n-1):
  print(rl[i],end = ' ')
  
 print("") 
 
nt = int(input())
for i in range(0,nt):
 n = int(input())
 l = list(map(int,input().strip().split(' ')))
 insFinder(n,l)
 
 

# cook your dish here
# cook your dish here
# cook your dish here
import math
def gcd(num1,num2):
 if(num2==0):
  return num1
 else:
  return gcd(num2,num1%num2)


t=int(input())
for i in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 l=[] #list with sublist starting and ending point of greater then 1         gcd
 sm=[]
 p1=0
 p2=0
 j=0
 while(j<n-1):
  if(gcd(a[j],a[j+1])!=1):
   p1=j+0
   while(j<n-1 and gcd(a[j],a[j+1])!=1):
    j+=1
   p2=j+0
   l.append([p1,p2])
   sm.append(p2-p1+1)
  else:
   j+=1
 #last ka first aur age k kuch elements KA consider krna bch gya
 #agr last aur first ka gcd!=1 to dono merge honge
 if(len(l)>0 and l[0][1]-l[0][0]<n-1):
  if(l[-1][1]==n-1 and l[0][0]==0):
   if(gcd(a[-1],a[0])!=1):
    #print(sm)
    sm[0]+=sm[-1]
    sm.pop()
    #print(sm)
  elif(gcd(a[-1],a[0])!=1 and l[0][0]==0):
   sm[0]+=1
  elif(gcd(a[-1],a[0])!=1 and l[-1][1]==n-1):
   sm[-1]+=1
  elif(gcd(a[-1],a[0])!=1):
   sm.append(2)
 
  w=[0]*(n+1)
  for j in range(len(sm)):
   for k in range(2,sm[j]+1):                #l[j][1]-l[j][0]+1 uska                 size h aur usko consider krne k liye +1 aur kiya h
    w[k]+=math.ceil((sm[j]-1)//(k-1))
  print(*w[2:])
 elif(len(l)>0):
  w=[0]*(n+1)
  if(gcd(a[-1],a[0])!=1):
   for j in range(len(sm)):
    for k in range(2,sm[j]+1):                #l[j][1]-l[j][0]+1                     uska size h aur usko consider krne k liye +1 aur kiya h
     w[k]+=math.ceil((sm[j]-1)//(k-1))+1
   print(*w[2:])
  else:
   for j in range(len(sm)):
    for k in range(2,sm[j]+1):                #l[j][1]-l[j][0]+1                     uska size h aur usko consider krne k liye +1 aur kiya h
     w[k]+=math.ceil((sm[j]-1)//(k-1))
   print(*w[2:])
 else:
  #print("No")
  w=[0]*(n+1)
  if(gcd(a[-1],a[0])!=1):
   w[2]=1
   print(*w[2:])
  else:
   print(*w[2:])

# cook your dish here
import math
def solveit(A,n):
 N=n
 G=[]
 for i in range(n):
  v=(math.gcd(A[i],A[(i+1)%N]))
  if (v==1):
   G.append(1)
  else:
   G.append(0)

 pos=-1
 for i in range(n):
  if (G[i]==1):
   pos=i
   break

 V=[]
 ans=[0 for i in range(N-1)]
 if (pos==-1):
  for i in range(N-1):
   ans[i]=math.ceil(N/(i+1))
 else:
  c=0
  for i in range(1,N+1):
   if (G[(pos+i)%N]==0):
    c=c+1

   else:
    if (c!=0):
     V.append(c)
    c=0

 
  for val in V:
   for i in range(min(val,N-1)):
    ans[i]=ans[i]+(val//(i+1))

 print(*ans)
   

 
for _ in range(int(input())):
 n=int(input())
 A=list(map(int,input().split()))
 solveit(A,n)



# cook your dish here
import math
def solveit(A,n):
 N=n
 G=[]
 for i in range(n):
  v=(math.gcd(A[i],A[(i+1)%N]))
  if (v==1):
   G.append(1)
  else:
   G.append(0)
 # print(G)
 pos=-1
 for i in range(n):
  if (G[i]==1):
   pos=i
   break

 V=[]
 ans=[0 for i in range(N-1)]
 if (pos==-1):
  for i in range(N-1):
   ans[i]=math.ceil(N/(i+1))
 else:
  c=0
  for i in range(1,N+1):
   if (G[(pos+i)%N]==0):
    c=c+1

   else:
    if (c!=0):
     V.append(c)
    c=0

 
  for val in V:
   for i in range(min(val,N-1)):
    ans[i]=ans[i]+(val//(i+1))

 print(*ans)
   

 
for _ in range(int(input())):
 n=int(input())
 A=list(map(int,input().split()))
 solveit(A,n)



# cook your dish here
import math
from collections import defaultdict
t=int(input())
for i in range(t):
 n=int(input())
 b=list(map(int,input().split()))
 j=0
 res=[]
 while(j<n):
  if math.gcd(b[j],b[(j+1)%n])>1:
   res.append(1)
  else:
   res.append(0)
  j+=1
 j=0
 f=0
 ans=[]
 while(j<n):
  if res[j]==0:
   f=1
   req=j
   break
  j+=1
 if f==0:
  j=1
  while(j<n):
   ans.append(math.ceil(n/j))
   j+=1
  print(*ans)

 else:
  j=req+1
  s=0
  while(j%n!=req):
   if res[j%n]==1:
    s+=1
   else:
    if s!=0:
     ans.append(s)
    s=0
   j+=1
  ans.append(s)
  d=defaultdict(lambda:0)
  j=0
  l=len(ans)

  while(j<l):
   p=ans[j]
   r=p
   while(r>=1):
    d[r]+=(p//r)
    r+=-1
   j+=1
  ans=[]
  r=1
  while(r<n):
   ans.append(d[r])
   r+=1
  print(*ans)

























# cook your dish here
import math
for _ in range(int(input())):
 n=int(input())
 A=list(map(int,input().split()))
 N=n
 G=[]
 for i in range(n):
  v=(math.gcd(A[i],A[(i+1)%N]))
  if (v==1):
   G.append(1)
  else:
   G.append(0)
 pos=-1
 for i in range(n):
  if (G[i]==1):
   pos=i
   break
 V=[]
 ans=[0 for i in range(N-1)]
 if (pos==-1):
  for i in range(N-1):
   ans[i]=math.ceil(N/(i+1))
 else:
  c=0
  for i in range(1,N+1):
   if (G[(pos+i)%N]==0):
    c=c+1
   else:
    if (c!=0):
     V.append(c)
    c=0
  for val in V:
   for i in range(min(val,N-1)):
    ans[i]=ans[i]+(val//(i+1))
 print(*ans)