"It does not matter how slowly you go as long as you do not stop." - Confucius
You are given an array $A_1, A_2, \ldots, A_N$ and an integer $K$. For each subarray $S = [A_l, A_{l+1}, \ldots, A_r]$ ($1 \le l \le r \le N$):
- Let's define an array $B$ as $S$ concatenated with itself $m$ times, where $m$ is the smallest integer such that $m(r-l+1) \ge K$.
- Next, let's sort $B$ and define $X = B_K$, i.e. as a $K$-th smallest element of $B$. Note that $|B| \ge K$.
- Then, let's define $F$ as the number of occurrences of $X$ in $S$.
- The subarray $S$ is beautiful if $F$ occurs in $S$ at least once.
Find the number of beautiful subarrays of $A$. Two subarrays $A_l, A_{l+1}, \ldots, A_r$ and $A_p, A_{p+1}, \ldots, A_q$ are different if $l \neq p$ or $r \neq q$.

-----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 space-separated 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 number of beautiful subarrays.

-----Constraints-----
- $1 \le T \le 5$
- $1 \le N \le 2,000$
- $1 \le K \le 10^9$
- $1 \le A_i \le 2000$ for each valid $i$

-----Subtasks-----
Subtask #1 (20 points): $1 \le N \le 200$
Subtask #2 (80 points): original constraints

-----Example Input-----
1
3 3
1 2 3

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

-----Explanation-----
Example case 1: There are six subarrays of $A$: $[1]$, $[2]$, $[3]$, $[1, 2]$, $[2, 3]$, $[1, 2, 3]$. The corresponding arrays $B$ are $[1, 1, 1]$, $[2, 2, 2]$, $[3, 3, 3]$, $[1, 2, 1, 2]$, $[2, 3, 2, 3]$, $[1, 2, 3]$.
Three of the subarrays are beautiful: $[1]$, $[1, 2]$ and $[1, 2, 3]$. For these subarrays, $X$ is $1$, $2$ and $3$ respectively (for example, for $S = [1, 2]$, $B = [1, 2, 1, 2]$ is sorted to $[1, 1, 2, 2]$ and $X = 2$ is the $3$-rd element). Then, $F = 1$ for each of these subarrays, and each of these subarrays contains $1$.

Difficulty: interview

Starter code:

Solutions:
from bisect import insort
from math import ceil
for _ in range(int(input())):
 n,k=list(map(int,input().split( )))
 array=list(map(int,input().split( )))
 ans=0
 index=[]
 for i in range(1,n+1):
  index.append(ceil(k/(ceil(k/i))))
 for i in range(n):
  count=[0]*(2001)
  temp=[]
  for j in range(i,n):
   count[array[j]]+=1
   insort(temp,array[j])
   #m=ceil(k/(j-i+1)) precalculate thes values in index array
   #t=ceil(k/m)
   x=temp[index[j-i]-1]
   f=count[x]
   if count[f]:
    ans+=1
 print(ans)


from bisect import insort
from math import ceil
for _ in range(int(input())):
 n,k=map(int,input().split( ))
 array=list(map(int,input().split( )))
 ans=0
 for i in range(n):
  count=[0]*(2001)
  temp=[]
  for j in range(i,n):
   count[array[j]]+=1
   insort(temp,array[j])
   m=ceil(k/(j-i+1))
   t=ceil(k/m)
   x=temp[t-1]
   f=count[x]
   if count[f]:
    ans+=1
 print(ans)

from math import ceil
def Beauty(array,f,n):
 i=0
 j=i
 ans=0
 while i<n and j<n:
  if array[j]==f:
   ans+=(n-j)*(j-i)+(n-j)
   i=j+1
   j=i
  else:
   j+=1
 return ans
from collections import defaultdict
for _ in range(int(input())):
 n,k=map(int,input().split( ))
 array=list(map(int,input().split( )))
 s=defaultdict(int)
 for v in array:
  s[v]+=1
 res=0
 for i in range(n):
  for j in range(i,n):
   b=array[i:j+1]
   b.sort()
   m=ceil(k/(j-i+1))
   t=ceil(k/m)
   x=b[t-1]
   f=b.count(x)
   if f in b:
    res+=1
   #res+=Beauty(array,f,n)
 print(res)

import bisect
for t in range(int(input())):
 n, k = map(int, input().split())
 arr = list(map(int, input().split()))
 arr.insert(0,0)
 c = 0
 pre = [0 for k in range(2001)]
 for i in range(1, 2001):
  m = (int(k / i)) + 1
  if(k % i == 0):
   m = m - 1
  x = (int(k / m)) + 1
  if(k % m == 0):
   x = x - 1
  pre[i] = x
 for i in range(1, n + 1):
  brr = [0 for k in range(2001)]
  lis = []
  for j in range(i, n + 1):
   brr[arr[j]] = brr[arr[j]] + 1
   bisect.insort(lis, arr[j])
   size = j - i + 1
   xt = pre[size]
   y = lis[xt-1]
   f = brr[y]
   if brr[f] > 0:
    c = c + 1
 print(c)

import sys
input=sys.stdin.readline 
from collections import defaultdict
from math import ceil 
from bisect import bisect_left as bl ,insort
for _ in range(int(input())):
 n,k=map(int,input().split())
 l=[int(i) for i in input().split()]
 ans=0
 for i in range(n):
  curr=[]
  cnt=[0]*(2002)
  for j in range(i,n):
   add=ceil(k/(j-i+1))
   #ind=bl(curr,l[j])
   insort(curr,l[j])
   cnt[l[j]]+=1 
   if k<=j-i+1:
    x=curr[k-1]
   else:
    x=curr[ceil(k/add)-1]
   z=cnt[x]
   if cnt[z]:
    ans+=1 
 print(ans)

import sys
input=sys.stdin.readline 
from collections import defaultdict
from math import ceil 
from bisect import bisect_left as bl 
for _ in range(int(input())):
 n,k=map(int,input().split())
 l=[int(i) for i in input().split()]
 cnt=0
 for i in range(n):
  curr=[]
  d=defaultdict(int)
  for j in range(i,n):
   add=ceil(k/(j-i+1))
   ind=bl(curr,l[j])
   curr.insert(ind,l[j])
   d[l[j]]+=1 
   if k<=j-i+1:
    x=curr[k-1]
   else:
    x=curr[ceil(k/add)-1]
   z=d[x]
   if d[z]:
    cnt+=1 
 print(cnt)

for _ in range(int(input())):
 n,k=map(int,input().split())
 from math import ceil 
 l=[int(i) for i in input().split()]
 cnt=0 
 from collections import defaultdict
 from bisect import bisect_left as bl 
 for i in range(n):
  curr=[]
  d=defaultdict(int)
  for j in range(i,n):
   add=ceil(k/(j-i+1))
   ind=bl(curr,l[j])
   curr.insert(ind,l[j])
   d[l[j]]+=1 
   if k<=j-i+1:
    x=curr[k-1]
   else:
    x=curr[ceil(k/add)-1]
   z=d[x]
   if d[z]:
    cnt+=1 
 print(cnt)

for _ in range(int(input())):
 n,k=map(int,input().split())
 from math import ceil 
 l=[int(i) for i in input().split()]
 cnt=0 
 for i in range(n):
  for j in range(i,n):
   add=ceil(k/(j-i+1))
   curr=l[i:j+1]
   curr.sort()
   if k<=j-i+1:
    x=curr[k-1]
   else:
    x=curr[ceil(k/add)-1]
   z=curr.count(x)
   if z in curr:
    cnt+=1 
 print(cnt)

import bisect
import sys
from sys import stdin, stdout
test = int(sys.stdin.readline())
while test > 0:
 test = test - 1
 nk = [int(x) for x in sys.stdin.readline().split()]
 n = nk[0]
 k = nk[1]
 arr = [int(x) for x in sys.stdin.readline().split()]
 arr.insert(0,0)
 c = 0
 pre = [0 for k in range(2001)]
 for i in range(1, 2001):
  m = (int(k / i)) + 1
  if(k % i == 0):
   m = m - 1
  x = (int(k / m)) + 1
  if(k % m == 0):
   x = x - 1
  pre[i] = x
 for i in range(1, n + 1):
  #print(arr[i], end = " ")
  brr = [0 for k in range(2001)]
  lis = []
  for j in range(i, n + 1):
   brr[arr[j]] = brr[arr[j]] + 1
   bisect.insort(lis, arr[j])
   #print(lis)
   size = j - i + 1
   xt = pre[size]
   y = lis[xt-1]
   f = brr[y]
   if brr[f] > 0:
    #print(i," ",j," ",y)
    c = c + 1
 print(c)

from math import ceil
from bisect import insort
for z in range(int(input())):
 n,k=list(map(int,input().split()))
 a=list(map(int,input().split()))
 c=0
 i=0
 pos=[]
 while i<n:
  pos.append(ceil(k/(ceil(k/(i+1)))))
  i+=1
 i=0
 while i<n-1:
  h=[]
  cl=[0]*2001
  j=0
  while i+j<n:
   cl[a[i+j]]+=1
   insort(h,a[i+j])
   x=h[pos[j]-1]
   f=cl[x]
   if cl[f]:c+=1
   j+=1
  i+=1
 print(c)


from math import ceil
from bisect import insort
for z in range(int(input())):
 n,k=list(map(int,input().split()))
 a=list(map(int,input().split()))
 i=0
 c=0
 while i<n-1:
  h=[]
  cl=[0]*2001
  j=0
  while i+j<n:
   cl[a[i+j]]+=1
   insort(h,a[i+j])
   m=ceil(k/(j+1))
   p=ceil(k/m)
   x=h[p-1]
   f=cl[x]
   if cl[f]:c+=1
   j+=1
  i+=1
 print(c)


from bisect import bisect_left

def BinarySearch(a, x):
 i = bisect_left(a, x)
 if i != len(a) and a[i] == x:
  return True
 else:
  return False

import math
for _ in range(int(input())):
 #arnab sucks
 ans=0
 N,k=[int(x) for x in input().split()]
 a=[int(x) for x in input().split()]
 for i in range(N):
  for j in range(i,N):
   S=a[i:j+1]
   S.sort()
   god=math.ceil(k/len(S))

   X=S[math.ceil(k/god)-1]
   F=0
   for z in S:
    if z ==X:
     F+=1
   if BinarySearch(S,F):
    ans+=1
 print(ans)


import heapq

t=int(input())
for y in range(t):
 (n, k )=(int(x) for x in input().split())
 places=[]
 for l in range(1,n+1):
  m=(k-1)//l+1
  shoot=m*l-k
  place=shoot//m+1
  places.append(place)
 A=[int(x) for x in input().split()]
 heaps=[[-x] for x in A]
 assert(len(A)==n)
 ans=A.count(1)
 for l in range(1,n):
  elements=[0]*2001
  for e in A[:l+1]:
   try:
    elements[e]+=1
   except:
    elements[e]=1
  for s in range(0,n-l):
   heapq.heappush(heaps[s],-A[s+l]) 
   if places[l]>2:
    reserve=[]
    for i in range(places[l]):
     reserve.append(heapq.heappop( heaps[s]))
    for r in reserve:
     heapq.heappush(heaps[s],r)
    x=-reserve[-1]
   elif (places[l]==2):
    x=max(-heaps[s][1],heaps[s][2])
   else:
    x=-heaps[s][0]
   f=elements[x]
   try:
    if elements[f]>0:
     ans+=1
   except:
    pass
   if s<n-l-1:
    try:
     elements[A[s]]-=1
     elements[A[s+l+1]]+=1
    except: 
     elements[A[s+l+1]]=1
 print(ans)

import bisect
import math
t=int(input())
while t>0:
 fp=0
 n,k=map(int,input().split())
 a=list(map(int,input().split()))
 
 for i in range(n):
  left=[]
  
  arr=[0]*2005
  for j in range(i,n):
   bisect.insort(left, a[j])
   arr[a[j]]+=1
   uhoy=math.ceil(k/(j-i+1))
   mc=int(((k-1)/uhoy))
   kpop=arr[left[mc]]
   if arr[kpop]>=1:
    fp+=1
 print(fp)
 t-=1

import bisect
import math
t=int(input())
while t>0:
 fp=0
 n,k=map(int,input().split())
 a=list(map(int,input().split()))
 
 for i in range(n):
  left=[]
  
  arr=[0]*2050
  for j in range(i,n):
   right = a[j]
   bisect.insort(left, right)
   arr[a[j]]+=1
   uhoy=math.ceil(k/(j-i+1))
   mc=int(math.ceil(k/uhoy))
   kpop=arr[left[mc-1]]
   if arr[kpop]>=1:
    fp+=1
 print(fp)
 t-=1

import bisect
import math
t=int(input())
while t>0:
 fp=0
 n,k=map(int,input().split())
 a=[int(o) for o in input().split()]
 
 for i in range(n):
  left=[]
  
  arr=[0]*2050
  for j in range(i,n):
   right = a[j]
   #pos = bisect.bisect(left, right)
   bisect.insort(left, right)
   arr[a[j]]+=1
   uhoy=math.ceil(k/(j-i+1))
   mc=int(math.ceil(k/uhoy))
   kpop=arr[left[mc-1]]
   if arr[kpop]>=1:
    fp+=1
 print(fp)
 t-=1

import bisect as b
t=int(input())
while(t):
 t-=1
 n,k=map(int,(input().split()))
 a=list(map(int,input().split()))
 c=0
 for i in range(n):
  x=[0]
  d=dict()
  for j in range(i,n):
   b.insort(x,a[j])
   y=k/(len(x)-1)
   if(d.get(a[j],-1)==-1):
    d[a[j]]=1
   else:
    d[a[j]]+=1
   if(int(y)!=y):
    y=int(y)+1
   y=int(y)
   z=k/y
   if(int(z)!=z):
    z=int(z)+1
   z=int(z)
   #print(d,x[z])
   q=d[x[z]]
   if(d.get(q,-1)!=-1):
    c+=1
 print(c)

import bisect as b
t=int(input())
while(t):
 t-=1
 n,k=map(int,(input().split()))
 a=list(map(int,input().split()))
 c=0
 for i in range(n):
  x=[0]
  d=dict()
  for j in range(i,n):
   b.insort(x,a[j])
   y=k/(len(x)-1)
   if(d.get(a[j],-1)==-1):
    d[a[j]]=1
   else:
    d[a[j]]+=1
   if(int(y)!=y):
    y=int(y)+1
   y=int(y)
   z=k/y
   if(int(z)!=z):
    z=int(z)+1
   z=int(z)
   #print(d,x[z])
   q=d[x[z]]
   if(d.get(q,-1)!=-1):
    c+=1
 print(c)

import bisect as b
t=int(input())
while(t):
 t-=1
 n,k=map(int,(input().split()))
 a=list(map(int,input().split()))
 c=0
 for i in range(n):
  x=[0]
  for j in range(i,n):
   b.insort(x,a[j])
   y=k/(len(x)-1)
   if(int(y)!=y):
    y=int(y)+1
   y=int(y)
   z=k/y
   if(int(z)!=z):
    z=int(z)+1
   z=int(z)
   q=1
   l=z-1
   while(l>=0):
    if(x[l]!=x[z]):
     break
    q+=1
    l-=1
   l=z+1
   #print(x,l)
   while(l<len(x)):
    if(x[l]!=x[z]):
     break
    l+=1
    q+=1
   l=b.bisect(x,q)
   if(x[l-1]==q):
    c+=1
 print(c)

import bisect as b
t=int(input())
while(t):
 t-=1
 n,k=map(int,(input().split()))
 a=list(map(int,input().split()))
 c=0
 for i in range(n):
  x=[0]
  for j in range(i,n):
   b.insort(x,a[j])
   y=k/(len(x)-1)
   if(int(y)!=y):
    y=int(y)+1
   y=int(y)
   z=k/y
   if(int(z)!=z):
    z=int(z)+1
   z=int(z)
   if(x.count(x[z]) in x):
    c+=1
 print(c)

import bisect as b
t=int(input())
while(t):
 t-=1
 n,k=map(int,(input().split()))
 a=list(map(int,input().split()))
 c=0
 for i in range(n):
  x=[0]
  for j in range(i,n):
   b.insort(x,a[j])
   y=k/(len(x)-1)
   if(int(y)!=y):
    y=int(y)+1
   y=int(y)
   z=k/y
   if(int(z)!=z):
    z=int(z)+1
   z=int(z)
   if(x.count(x[z]) in x):
    c+=1
 print(c)

from collections import Counter
from math import ceil
test=int(input())
for _ in range(test):
 n,k=list(map(int,input().split()))
 a=list(map(int,input().split()))
 total=0
 for i in range(n):
  for j in range(i+1,n+1):
   subarray=a[i:j]
   length=j-i
   c=Counter(subarray)
   m = (k//length) if (k%length==0) else (k//length+1)
   kth=sorted(subarray)[ceil(k/m)-1]
   F=c[kth]
   if F in c:
    total+=1
 print(total)
   
   


import math
import heapq
def counting_sort(array1, max_val):
 m = max_val + 1
 count = [0] * m
 for a in array1:
  count[a] += 1
 i = 0
 for a in range(m):
  for c in range(count[a]):
   array1[i] = a
   i += 1
 return array1
for _ in range(int(input())):
 n,k=list(map(int,input().split()))
 l=list(map(int,input().split()))
 M=[]
 ans=0
 for i in range(n):
  for j in range(i,n):
   m=math.ceil(k/(j-i+1))
   gt=(k-1)//m
   M.append(gt)
  break
 for i in range(n):
  max=-1
  s=set()
  d={}
  hallo_frnd={}
  for j in range(i,n):
   x=None
   value=M[j-i]
   if l[j] not in d:
    d[l[j]]=1
   else:
    d[l[j]]+=1
   if l[j]>max:
    max=l[j]
   if value not in s:
    ####
    s.add(value)
    x=max
    hallo_frnd[value]=max
   else:
    if l[j]<hallo_frnd[value]:
     yt=l[i:j+1]
     heapq.heapify(yt)
     x=heapq.nsmallest(value+1,yt)[-1]
     hallo_frnd[value]=x
    else:
     x=hallo_frnd[value]
   if d[x] in d:
    ans+=1
 print(ans)