Chef made $N$ pieces of cakes, numbered them $1$ through $N$ and arranged them in a row in this order. There are $K$ possible types of flavours (numbered $1$ through $K$); for each valid $i$, the $i$-th piece of cake has a flavour $A_i$.
Chef wants to select a contiguous subsegment of the pieces of cake such that there is at least one flavour which does not occur in that subsegment. Find the maximum possible length of such a subsegment of cakes.

-----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 two integers $N$ and $K$.
- 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 ― the maximum length of a valid subsegment.

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

-----Subtasks-----
Subtask #1 (50 points):
- $N \le 10^3$
- $K = 2$
- the sum of $N$ over all test cases does not exceed $10^4$
Subtask #2 (50 points): original constraints

-----Example Input-----
2
6 2
1 1 1 2 2 1
5 3
1 1 2 2 1

-----Example Output-----
3
5

Difficulty: interview

Starter code:

Solutions:
def main():
 t= int(input())
 while(t!=0):
  n,k = list(map(int , input().split()))
  arr = list(map(int, input().split()))
  freq = [0]*100001
  k=k-1
  st=0
  end=0
  currentCount=0
  previousElement = 0
  for i in range(n):
   freq[arr[i]]+=1
   if(freq[arr[i]]==1):
    currentCount+=1

   while(currentCount>k):
    freq[arr[previousElement]]-=1
    if(freq[arr[previousElement]]==0):
     currentCount-=1

    previousElement+=1

   if(i-previousElement+1 >= end-st+1):
    end=i
    st=previousElement

  print(end-st+1)
  t=t-1

def __starting_point():
 main()





__starting_point()

# cook your dish here
def main():
 t=int(input())
 while(t!=0):
  n,k = map(int, input().split())
  arr = list(map(int, input().split()))
  freq = [0]*100001
  k=k-1
  st=0
  end=0
  currentCount=0
  previousElement =0
  for i in range(n):
   freq[arr[i]]+=1
   if(freq[arr[i]]==1):
    currentCount+=1

   while(currentCount>k):
    freq[arr[previousElement]]-=1
    if(freq[arr[previousElement]]==0):
     currentCount-=1
    previousElement+=1

   if(i-previousElement+1 >= end-st+1):
    end=i
    st = previousElement

  print(end-st+1)
  t=t-1

def __starting_point():
 main()
__starting_point()

# cook your dish here
t = int(input())
for _ in range(t):
 n,k = map(int, input().split())
 arr = list(map(int, input().split()))
 i = 0
 maxi = 0
 visited = set()
 count = 0
 sec = -1
 f = 0
 while i<n:
  visited.add(arr[i])
  if len(visited)==2 and f==0:
   sec = i
   f = 1
  if len(visited)==k:
   maxi = max(count, maxi)
   count = 1
   i = sec
   visited = {arr[i]}
   f = 0
  else:
   count = count + 1
  i = i + 1
 maxi = max(count, maxi)
 print(maxi)

# cook your dish here
t = int(input())
for _ in range(t):
 n,k = map(int, input().split())
 arr = list(map(int, input().split()))
 i = 0
 maxi = 0
 visited = set()
 count = 0
 sec = -1
 f = 0
 while i<n:
  visited.add(arr[i])
  if len(visited)==2 and f==0:
   sec = i
   f = 1
  if len(visited)==k:
   maxi = max(count, maxi)
   count = 1
   visited = {arr[i]}
   i = sec
   f = 0
  else:
   count = count + 1
  i = i + 1
 maxi = max(count, maxi)
 print(maxi)

# cook your dish here
for _ in range(int(input())):
 n,k=list(map(int, input().split()))
 l=list(map(int, input().split()))
 ans, temp = 0, 0
 
 if k==2:
  l1=[0, 0]
  for i in l:
   l1[i-1]=1 
   temp+=1 
   if l1==[1, 1]:
    ans=max(ans, (temp-1))
    l1=[0, 0]
    l1[i-1]=1 
    temp=1 
  
 else:
  l1=set()
  for i in range(n):
   l1.add(l[i])
   temp=1 
   for j in range(i+1, n):
    if l[j] in l1:
     temp+=1 
     
    else:
     if len(l1)==k-1:
      l1=set()
      ans=max(ans, temp)
      break
     
     else:
      l1.add(l[j])
      temp+=1
      
   ans=max(ans, temp)
     
     
 print(max(ans, temp))

# cook your dish here
for _ in range(int(input())):
 n,k=list(map(int, input().split()))
 l=list(map(int, input().split()))
 ans, temp = 0, 0
 
 if k==2:
  l1=[0, 0]
  for i in l:
   l1[i-1]=1 
   temp+=1 
   if l1==[1, 1]:
    ans=max(ans, (temp-1))
    l1=[0, 0]
    l1[i-1]=1 
    temp=1 
  
 else:
  l1=[]
  for i in range(n):
   l1.append(l[i])
   temp=1 
   for j in range(i+1, n):
    if l[j] in l1:
     temp+=1 
     
    else:
     if len(l1)==k-1:
      l1=[]
      ans=max(ans, temp)
      break
     
     else:
      l1.append(l[j])
      temp+=1
      
   ans=max(ans, temp)
     
     
 print(max(ans, temp))

# cook your dish here
for _ in range(int(input())):
 n,k=list(map(int, input().split()))
 l=list(map(int, input().split()))
 l1=[0]*k 
 l2=[1]*k
 ans, temp = 0, 0

 for i in l:
  l1[i-1]=1 
  temp+=1 
  if l1==l2:
   ans=max(ans, (temp-1))
   l1=[0]*k
   l1[i-1]=1 
   temp=1 
   
 print(max(ans, temp))

# cook your dish here
n=int(input())
for i in range(n):
 a,b=[int(i) for i in input().split()]
 l=[int(i) for i in input().split()]
 start=0
 end=0
 d=[]
 min=-10**9
 for j in range(0,len(l)):
  d.append(l[j])
  end=end+1
  if(len(set(d))<b):
   pass
  else:
   end=end-1
   start=end
   while(len(set(d))>=b):
    d.pop(0)
  if(len(d)>min):
   min=len(d)
 print(min)

# cook your dish here
n=int(input())
for i in range(n):
 a,b=[int(i) for i in input().split()]
 l=[int(i) for i in input().split()]
 start=0
 end=0
 d=[]
 answer=[]
 for j in range(0,len(l)):
  d.append(l[j])
  end=end+1
  if(len(set(d))<b):
   pass
  else:
   end=end-1
   start=end
   while(len(set(d))>=b):
    d.pop(0)
  answer.append(len(d))
 print(max(answer))

# cook your dish here
def sol(arr,n,k):
 m=-1
 for i in range(n):
  flag=0
  count=1 
  s=set()
  s.add(arr[i])
  temp=i
  for j in range(i+1,n):
   if arr[j] not in s:
    if len(s)==k-1:
     flag=1
    else:
     s.add(arr[j])
     count+=1 
   else:
    count+=1
   if flag==1:
    break
  if count>m:
   m=count
 return m
 
test=int(input())
for _ in range(test):
 n,k = map(int,input().split())
 arr = list(map(int,input().split()))
 if k==2:
  mi=sol(arr,n,k)
  print(mi)
  continue
 freq=[0]*n
 i=0
 j=0
 c=0
 l=0
 mx=-1
 k-=1
 for x in range(n):
  freq[arr[x]]+=1 
  if freq[arr[x]]==1:
   c+=1 
  while(c>k):
   freq[arr[l]]-=1
   if freq[arr[l]]==0:
    c-=1
   l+=1 
  if x-l+1>=j-i+1:
   j=x
   i=l
 print(j-i+1)

#
def sol(arr,n,k):
 m=-1
 for i in range(n):
  flag=0
  count=1 
  s=set()
  s.add(arr[i])
  temp=i
  for j in range(i+1,n):
   if arr[j] not in s:
    if len(s)==k-1:
     flag=1
    else:
     s.add(arr[j])
     count+=1 
   else:
    count+=1
   if flag==1:
    break
  if count>m:
   m=count
 return m
for _ in range(int(input())):
 n,k = list(map(int,input().split()))
 arr = list(map(int,input().split()))
 if k==2:
  mi=sol(arr,n,k)
  print(mi)
  continue
 freq=[0]*n
 i=0
 j=0
 c=0
 l=0
 mx=-1
 k-=1
 for x in range(n):
  
  freq[arr[x]]+=1 
  #print(freq)
  if freq[arr[x]]==1:
   c+=1 
  while(c>k):
   freq[arr[l]]-=1
   if freq[arr[l]]==0:
    c-=1
   l+=1 
  if x-l+1>=j-i+1:
   j=x
   i=l

 print(j-i+1)
    
    
   


#

for _ in range(int(input())):
 n,k = list(map(int,input().split()))
 arr = list(map(int,input().split()))
 m=-1
 for i in range(n):
  flag=0
  count=1 
  s=set()
  s.add(arr[i])
  for j in range(i+1,n):
   if arr[j] not in s:
    if len(s)==k-1:
     flag=1
    else:
     s.add(arr[j])
     count+=1 
   else:
    count+=1
   if flag==1:
    break
  if count>m:
   m=count
 print(m)
    
    
    
   


for T in range(int(input())):
 n,k=list(map(int,input().split()))
 a=list(map(int,input().split()))
 if(len(set(a))<k):
  print(len(a))
 else:
  f,t,c=[],[],1
  key=a[0]
  for i in range(1,n):
   if(a[i]==key):
    c+=1
   else:
    f.append(c)
    t.append(key)
    key=a[i]
    c=1
  f.append(c)
  t.append(key)
  check=[0]*(k+1)
  i,start,l,m,uni=0,0,0,0,0
  while(i < len(t) and start < len(t)):
   check[t[i]]+=1
   if(check[t[i]]==1):
    uni+=1
   if(uni==k):
    check[t[i]]-=1
    m=max(m,l)
    check[t[start]]-=1
    if(check[t[start]]==0):
     uni-=1
    l-=f[start]
    start+=1
    uni-=1
    continue
   l+=f[i]
   i+=1
  m=max(m,l)
  print(m)
    
    

    
   
   
  
    
   


for T in range(int(input())):
 n,k=list(map(int,input().split()))
 a=list(map(int,input().split()))
 if(len(set(a))<k):
  print(len(a))
 else:
  f,t,c=[],[],1
  key=a[0]
  for i in range(1,n):
   if(a[i]==key):
    c+=1
   else:
    f.append(c)
    t.append(key)
    key=a[i]
    c=1
  f.append(c)
  t.append(key)
  check,uni,start,i=[],0,0,0
  l,m=0,0
  while(i<len(t) and start<len(t)):
   if(t[i] not in check):
    uni+=1
   if(uni==k):
    m=max(m,l)
    check.remove(t[start])
    if(t[start] not in check):
     uni-=1
    uni-=1
    l-=f[start]
    start+=1
    continue
   check.append(t[i])
   l+=f[i]
   i+=1
  m=max(m,l)
  print(m)

    
   
   
  
    
   


for _ in range(int(input())):
 ip=list(map(int,input().split()))
 n=ip[0]
 k=ip[1]
 l=list(map(int,input().split()))
 d={}
 i=0
 start=0
 end=0
 j=0
 m=0
 while j<n:
  d.setdefault(l[j],0)
  d[l[j]]+=1
  if(len(d)>=k):
   start=i
   #print(start,end=" ")
   end=j
   #print(end)
   #print(d)
   if d[l[i]]>1 :
    d[l[i]]-=1 
   else:                       #1 1 2 2 1
    d.pop(l[i])
   #print(d)
   if d[l[j]]>1 :
    d[l[j]]-=1 
   else:
    d.pop(l[j])
   #print(d)
   j-=1
   i+=1
  start=i
  end=j+1
  if m<=end-start:
   m=end-start
  #print(start,end)
  j+=1 #1 1 1 2 2 1
   
 print(m) 

for _ in range(int(input())):
 ip=list(map(int,input().split()))
 n=ip[0]
 k=ip[1]
 l=list(map(int,input().split()))
 d={}
 i=0
 start=0
 end=0
 j=0
 m=0
 while j<n:
  d.setdefault(l[j],0)
  d[l[j]]+=1
  if(len(d)>=k):
   start=i
   #print(start,end=" ")
   end=j
   #print(end)
   #print(d)
   if d[l[i]]>1 :
    d[l[i]]-=1 
   else:                       #1 1 2 2 1
    d.pop(l[i])
   #print(d)
   if d[l[j]]>1 :
    d[l[j]]-=1 
   else:
    d.pop(l[j])
   #print(d)
   j-=1
   i+=1
  start=i
  end=j+1
  if m<=end-start:
   m=end-start
  #print(start,end)
  j+=1 #1 1 1 2 2 1
   
 print(m) 

t=int(input())
while(t>0):
 n,k=list(map(int,input().split()))
 a=list(map(int,input().split()))
 l=[]
 mx=-1000000000
 start=0
 for end in range(n):
  l.append(a[end])
  while(len(set(l))>=k):
   l.pop(0)
   start+=1
  if(end-start+1>mx):
   mx=end-start+1
 print(mx)
 t=t-1


for _ in range(int(input())):
 n, k = list(map(int, input().split()))
 x = list(map(int, input().split()))
 l = 0
 r = 0
 ans = 0
 d= {i + 1: 0 for i in range(k)}
 s=set()
 while l <= r < n:
  if len(s) != k:
   s.add(x[r])
   d[x[r]] += 1
   if len(s) != k:
    ans = max(ans, r - l + 1)
   r += 1
  else:
   d[x[l]] -= 1
   if d[x[l]] == 0:
    s.remove(x[l])
   l += 1
 print(ans)


# cook your dish here
for u in range(int(input())):
 n,k=list(map(int,input().split()))
 l=list(map(int,input().split()))
 c=1
 m=0
 for i in range(n-1):
  if(l[i]==l[i+1]):
   c+=1
   m=max(m,c)
  else:
   c=1
 m=max(m,c)
 print(m)


def search(l,n,k):
 r=[]
 o=[]
 p=[]
 t=[]
 e=[]
 for i in range(k):
  o.append(-1)
 for i in range(n):
  r.append(i)
  for j in range(1,k+1,1):
   if(l[i]==j):
    o.append(i)
   else:
    o.append(o[len(o)-k])
    
 
 
 for i in range(k,len(o),k):
  for j in range(k):
   p.append(o[i+j])
  q=min(p)
  t.append(q)
  p.clear()
 
 
 for i in range(len(r)):
  y=r[i]-t[i]
  e.append(y)
  
 print(max(e))
  
  




t=int(input())

for i in range(t):
 n,k=map(int,input().split())
 l=list(map(int,input().split()))
 search(l,n,k)

import sys
from collections import defaultdict
def fin(): return sys.stdin.readline().strip()
def fout(s, end="\n"): sys.stdout.write(str(s)+end)

t = int(input())
while t>0:
 t -= 1
 n, k = list(map(int, fin().split()))
 a = [int(x) for x in fin().split()]
 freq = defaultdict(int)
 freq[a[0]] += 1
 temp = set([a[0]])
 ans = 1
 prev = 0
 for i in range(1, n):

  freq[a[i]] += 1
  temp.add(a[i])

  if len(temp) < k:
   ans = max(ans, i-prev+1)
  else:
   while len(temp) >= k:
    freq[a[prev]] -= 1
    if freq[a[prev]] == 0:
     temp.remove(a[prev])
    prev += 1
   
 print(ans)





for _ in range (int(input())):
 n,k = [int(i) for i in input().split()]
 a = [int(i) for i in input().split()]
 ind = [[] for i in range (k)]
 for i in range(n):
  ind[a[i]-1].append(i)
 maxi = 0
 flag = 0
 for i in ind:
  if len(i)==0:
   flag = 1
   break
  maxi = max(maxi,i[0])
  for j in range (1,len(i)):
   maxi = max(i[j]-i[j-1]-1,maxi)
  maxi = max(n-i[-1]-1,maxi)
 if flag == 1:
  print(n)
 else:
  print(maxi)

for _ in range(int(input())):
 n, k = list(map(int, input().split()))
 a = list(map(int, input().split()))
 p = 0
 sm = 0
 ans = 0
 d = dict()
 for i in range(n):
  d[a[i]] = d.get(a[i], 0) + 1
  if d[a[i]] == 1:
   sm += 1
  if sm == k:
   ans = max(ans, i - p)
   while sm == k:
    d[a[p]] = d[a[p]] - 1
    p += 1
    if d[a[p-1]] == 0:
     sm -= 1
     break
 ans = max(ans, n - p)
 if ans == 0:
  ans = n
 print(ans)


for _ in range(int(input())):
 n,k = map(int , input().split())
 arr = list(map(int , input().split()))
 i,j,ans = 0,0,0
 s= set()
 while(i < n and j < n):
  s.add(arr[j])
  if(len(s) < k):
   ans = max(ans,j - i + 1)
   j += 1
  else:
   b = arr[i]
   i += 1
   if(b not in arr[i:j + 1] and b in s):
    s.remove(b)
 print(ans)