Chef has a sequence $A_1, A_2, \ldots, A_N$. For a positive integer $M$, sequence $B$ is defined as $B = A*M$ that is, appending $A$ exactly $M$ times. For example, If $A = [1, 2]$ and $M = 3$, then $B = A*M = [1, 2, 1, 2, 1, 2]$
You have to help him to find out the minimum value of $M$ such that the length of the longest strictly increasing subsequence is maximum possible.

-----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 one integer ― the minimum value of $M$.

-----Constraints-----
- $1 \le T \le 500$
- $1 \le N \le 2*10^5$
- $1 \le A_i \le 10^9$
- It's guaranteed that the total length of the sequence $A$ in one test file doesn't exceed $2*10^6$

-----Sample Input:-----
3
2
2 1
2
1 2
5
1 3 2 1 2

-----Sample Output:-----
2
1
2

-----Explanation:-----
In the first test case, Choosing $M = 2$ gives $B = [2, 1, 2, 1]$ which has a longest strictly increasing sequence of length $2$ which is the maximum possible.
In the second test case, Choosing $M = 1$ gives $B  = [1, 2]$ which has a longest strictly increasing sequence of length $2$ which is the maximum possible.

Difficulty: interview

Starter code:

Solutions:
def mForMaxSeq(arr, n):
    eim = dict()
    for i in range(n):
        if arr[i] in eim:
            eim[arr[i]].append(i)
        else:
            eim[arr[i]] = [i]
    
    keys = sorted(eim.keys())
    
    # print(eim, keys)

    connected = False
    count = 0
    pI = -1

    nKeys = len(keys)
    for i in range(nKeys-1):
        
        if not connected:
            pI = eim[keys[i]][0]
            
            for idx in eim[keys[i+1]]:
                if idx >pI:
                    connected = True
                    count += 1
                    pI = idx
                    break
        else:
            connected = False

            for idx in eim[keys[i+1]]:
                if idx > pI:
                    connected = True
                    count += 1
                    pI = idx
                    break

    
    return (nKeys - count)


def __starting_point():
    for _ in range(int(input())):
        n = int(input())
        arr = list(map(int, input().split()))
        
        print(mForMaxSeq(arr, n))
        
        

__starting_point()

import collections
from sys import *
import bisect as bs

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = 1
    d = {}
    for i in range(n):
        if(a[i] not in d):
            d[a[i]] = []
        d[a[i]].append(i)
        
    l = list(d.keys())
    l.sort()
    c = 0
    
    for j in l:
        ln = len(d[j])
        v = bs.bisect_left(d[j],c)
        if(v==ln):
            c = d[j][0] + 1
            s +=1
            continue
        c = d[j][v] + 1
    print(s)

def findM(A, n):
    elemIdxMap = dict()
    for i in range(n):
        if A[i] in elemIdxMap:
            elemIdxMap[A[i]].append(i)
        else:
            elemIdxMap[A[i]] = [i]
    
    keys = sorted(elemIdxMap.keys())
    
    # print(elemIdxMap, keys)

    connected = False
    count = 0
    prevIdx = -1

    nKeys = len(keys)
    for i in range(nKeys-1):
        
        if not connected:
            prevIdx = elemIdxMap[keys[i]][0]
            
            for idx in elemIdxMap[keys[i+1]]:
                if idx >prevIdx:
                    connected = True
                    count += 1
                    prevIdx = idx
                    break
        else:
            connected = False

            for idx in elemIdxMap[keys[i+1]]:
                if idx > prevIdx:
                    connected = True
                    count += 1
                    prevIdx = idx
                    break

        # print(keys[i], count, prevIdx)
    # if count == nKeys - 1:
    #     return 1
    # else:
    #     return (nKeys - count)
    # print(nKeys, count)
    return (nKeys - count)


def __starting_point():
    for _ in range(int(input())):
        n = int(input())
        A = list(map(int, input().split()))
        
        print(findM(A, n))
        # print(findM([1, 3, 2, 1, 2], 5))
        

__starting_point()

t = int(input())
for j in range(t):
    n = int(input())
    l = list(map(int,input().split()))
    s = list(set(l))
    s.sort()
    dic = {}
    le = {}
    for j in s:
        dic[j] = []
        le[j] = 0
    for j in range(n):
        dic[l[j]].append(j+1)
        le[l[j]]+=1
    stack = [dic[s[0]][0]]
    z = 0
    m = 1
    x = len(s)
    for j in range(1,x):
        flag = 0
        for k in range(le[s[j]]):
            if dic[s[j]][k]+(m-1)*n>stack[z]:
                stack.append(dic[s[j]][k]+(m-1)*n)
                z+=1
                flag = 1
                break
        if flag==0:
            m+=1
            stack.append(dic[s[j]][0]+(m-1)*n)
            z+=1
    print(m)

for _ in range(int(input())):
    n = int(input())
    l = list(map(int,input().split()))
    u = list(set(l))
    u.sort()
    d ={}
    for i in u:
        d[i] = []
    for i in range(n):
        d[l[i]].append(i)
    f = d[u[0]][0]
    p = 1
    m = 1
    while p < len(u):
        if d[u[p]][-1]>f:
            for j in d[u[p]]:
                if j>f:
                    f = j
                    p+=1
                    break
        else:
            m += 1
            f = d[u[p]][0]
            p+=1
    print(m)
    
    
                
                
                


from collections import defaultdict
from bisect import bisect_right

I = input
t = int(I())
for _ in range(t):
  I()
  d = defaultdict(list)
  for i, x in enumerate(map(int, I().split())):
    d[x].append(i)
  i, m = -1, 1
  for x in sorted(d):
    l = d[x]
    j = bisect_right(l, i)
    if j == len(l):
      m += 1
      j = 0
    i = l[j]
  print(m)


from collections import defaultdict
for _ in range(int(input())):
    n = int(input())
    s = [int(i) for i in input().split()]
    w = defaultdict(list)
    for i in range(n):
        w[s[i]].append(i)
    typ = len(w)
    keys = sorted(list(w.keys()))
    length = len(keys)
    ele_count = 1
    i = 1
    rnd = 0
    val = keys[0]
    pos = w[keys[0]][0]
    while ele_count < typ:
        if w[keys[ele_count]][-1] < pos:
            rnd+=1
            pos = w[keys[ele_count]][0]
        else:
            i = 0
            while i < len(w[keys[ele_count]]) and w[keys[ele_count]][i]<=pos:
                i+=1
            pos = w[keys[ele_count]][i]
        ele_count+=1
    print(rnd+1)


from collections import defaultdict
from bisect import bisect_right

I = input
t = int(I())
for _ in range(t):
  I()
  d = defaultdict(list)
  for i, x in enumerate(map(int, I().split())):
    d[x].append(i)
  i, m = -1, 1
  for x in sorted(d):
    l = d[x]
    j = bisect_right(l, i)
    i = l[j % len(l)]
    m += j // len(l)
  print(m)


import collections
import bisect
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    d=collections.defaultdict(list)
    c,find,ans,l=0,0,0,[]
    for i in range(n):
        if a[i] not in d:
            l.append(a[i])
            c+=1
        d[a[i]].append(i)
    l.sort()
    for i in range(c):
        if i==0:
            ans+=1
            find=d[l[i]][0]+1
        else:
            k=bisect.bisect_left(d[l[i]],find)
            if k==0:
                find=d[l[i]][k]+1
            elif k==len(d[l[i]]):
                find=d[l[i]][0]+1
                ans+=1
            else:
                find=d[l[i]][k]+1
    print(ans)
            

    
    


from sys import stdin

for _ in range(int(stdin.readline())):
    n = int(stdin.readline())
    arr = list(map(int,stdin.readline().split()))
    final = {}
    m = sorted(list(set(arr)))
    count = 0
    d = {}
    for i in range(n):
        if arr[i] in d:
            d[arr[i]].append(i)
        else:
            d[arr[i]] = [i]
            
    pos = d[m[0]][0]
    j = 1
    while(j < len(m)):
        k = None
        for item in d[m[j]]:
            if item > pos:
                k = item
                break
        if k != None:
            j += 1
            pos = k
        else:
            count += 1
            pos = -1
    print(count+1)


# cook your dish here
import collections
import bisect
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    d=collections.defaultdict(list)
    c=0
    l=[]
    for i in range(n):
        if a[i] not in d:
            l.append(a[i])
            c+=1
        d[a[i]].append(i)
    l.sort()
    find=0
    ans=0
   # print(l)
   # print(d)
    for i in range(c):
        if i==0:
            ans+=1
            find=d[l[i]][0]+1
        else:
            k=bisect.bisect_left(d[l[i]],find)
           # print(k,find,l[i])
            if k==0:
                find=d[l[i]][k]+1
            elif k==len(d[l[i]]):
                find=d[l[i]][0]+1
                ans+=1
            else:
                find=d[l[i]][k]+1
       # print(ans)
    print(ans)
            

    
    


from collections import defaultdict
from bisect import bisect_right

I = input
t = int(I())
for _ in range(t):
  I()
  d = defaultdict(list)
  for i, x in enumerate(map(int, I().split())):
    d[x].append(i)
  i, m = -1, 1
  for x in sorted(d):
    l = d[x]
    j = bisect_right(l, i)
    if j < len(l):
      i = l[j]
    else:
      m += 1
      i = l[0]
  print(m)


from collections import defaultdict
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int,input().split()))
    ans = 1
    d = defaultdict(list)
    for i in range(n):
        d[arr[i]].append(i+1)
    ind = -10**10
    uno = list(set(arr))
    uno.sort()
    for i in uno:
        f = 0
        f2 = 0 
        k = 0
        op = d[i]
        for j in op:
            if f2==0:
                f2 = 1
                ck = j
            if j>ind:
                ind = j
                f = 1
                break
        if f==0:
            ind = ck
            ans+=1
    print(ans)

t=int(input())
while(t):
    t-=1
    n=int(input())
    a=list(map(int,input().split()))
    s=list(set(a))
    s.sort()
    ind=dict()
    for i in range(n):
        if(a[i] in ind):
            ind[a[i]].append(i)
        else:
            ind[a[i]]=[i]

    s1=1
    ref=-1
    for i in s:
        flag=0
        for j in ind[i]:
            if(j>ref):
                ref=j
                flag=1
                break
        if(flag==0):
            s1+=1
            ref=ind[i][0]     
    print(s1)


def bs(x, prev, pict):
    l = 0
    r = len(pict[x]) - 1
    while l <= r:
        if r - l < 5:
            for i in range(l, r + 1):
                if pict[x][i] > prev:
                    return pict[x][i]
            return -1
        mid = (l + r) // 2
        if pict[x][mid] < prev:
            l = mid + 1
        else:
            r = mid
    return -1


t = int(input())
for _ in range(t):
    n = int(input())
    s = list(map(int, input().split()))
    li = []
    pict = {}
    for i in range(len(s)):
        if pict.get(s[i]) is None:
            pict[s[i]] = []
            li.append(s[i])
        pict[s[i]].append(i + 1)
    li.sort()
    count = 1
    prev = 0
    i=len(li)
    for i in range(len(li)):
        x = bs(li[i], prev, pict)
        if x != -1:
            prev = x
        else:
            count += 1
            prev = pict[li[i]][0]
    print(count)


for T in range(int(input())):
    N = int(input())
    a = list(map(int, input().split()))
    d = {}
    elements = []
    for i in range(N):
        if a[i] not in d:
            d[a[i]] = [i]
            elements.append(a[i])
        else:
            d[a[i]].append(i)
    elements.sort()
    M = 1
    prev_index = d[elements[0]][0]
    for i in range(1, len(elements)):
        flag = True
        for j in range(len(d[elements[i]])):
            if prev_index < d[elements[i]][j]:
                flag = False
                prev_index = d[elements[i]][j]
                break
        if flag:
            M += 1
            prev_index = d[elements[i]][0]
    print(M)


t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    b=set(a)
    b=list(b)
    b.sort()
    c=dict()
    for i in range(n):
        if(a[i] in c):
            c[a[i]].append(i)
        else:
           c[a[i]]=[i]
   
    index=-1
    count=0
    for i in range(len(b)):
        r=c[b[i]]
        flag=0
        for j in range(len(r)):
            if(r[j]>index):
                flag=1
                index=r[j]
                break
        if(flag!=1):
            index=r[0]
            count+=1
        
    print(count+1)


from collections import defaultdict
for _ in range(int(input())):
    n = int(input())
    s = list(map(int, input().split()))
    r = defaultdict(list)
    for i in range(n):
        r[s[i]].append(i)
    t = sorted(r.keys())
    N = len(t)
    l = r[t[0]][0]
    ans = 1
    for i in range(1, N):
        flag = 0
        for j in r[t[i]]:
            if j >= l:
                l = j
                flag = 1
                break
        if flag == 0:
            ans += 1
            l = r[t[i]][0]
    print(ans)


def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    # from math import *
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    out = sys.stdout.write
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9)+7

    for t in range(int(data())):
        n=int(data())
        A=mdata()
        d=dd(list)
        for i in range(n):
            d[A[i]].append(i)
        l=sorted(d.keys())
        cnt=1
        ind=d[l[0]][0]
        for i in range(1,len(l)):
            k=bl(d[l[i]],ind)
            if k==len(d[l[i]]):
                cnt+=1
                ind=d[l[i]][0]
            else:
                ind=d[l[i]][k]
        print(cnt)

def __starting_point():
    main()
__starting_point()

from sys import stdin
input = stdin.readline

from bisect import bisect_right

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    d = {i: [] for i in a}

    for i, j in enumerate(a):
        d[j].append(i)

    ans = 1

    l = tuple(r[1] for r in sorted(d.items()))
    p = 0

    for i in range(len(l) - 1):
        x = bisect_right(l[i+1], l[i][p])

        if x == len(l[i+1]):
            ans += 1
            p = 0
        else:
            p = x

    print(ans)


t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(x) for x in input().strip().split()]
    a = [(a[i],i) for i in range(n)]
    a.sort()
    res=1
    prev=0
    prev_ind = -1
  
    i=0
    while i<n:
        if a[i][1]>prev_ind:
            prev_ind = a[i][1]
            prev = a[i][0]
            while i<n and a[i][0]==prev:
                i+=1
        else:
            prev = a[i][0]
            flag = False
            mn=a[i][1]
            while i<n and a[i][0]==prev:
                if a[i][1]>prev_ind:
                    prev_ind=a[i][1]
                    flag = True
                    break
                i+=1
            if flag:
                while i<n and a[i][0]==prev:
                    i+=1
            else:
                res+=1
                prev_ind=mn
    print(res)



# cook your dish here
import bisect

def solve(arr,n,ans):
    indices = {}
    dist_vals = []
    for i in range(n):
        if arr[i] not in list(indices.keys()):
            indices[arr[i]] = []
            dist_vals.append(arr[i])

        indices[arr[i]].append(i)

    dist_vals.sort()
    m = 1
    index = -1
    i = 0
    while i < len(dist_vals):
        x = dist_vals[i]
        index = bisect.bisect(indices[x],index)
        if index == len(indices[x]):
            m += 1
            index = -1
        else:
            index = indices[x][index]
            i += 1

    ans.append(m)

def main():
    t = int(input())
    ans = []
    for i in range(t):
        n = int(input())
        arr = list(map(int,input().split()))
        solve(arr,n,ans)

    for i in ans:
        print(i)


main()


from collections import defaultdict
import bisect
t = int(input())
for i in range(t):
    n = int(input())
    A = [int(j) for j in input().split()]
    d = defaultdict(list)
    for j,i in enumerate(A):
        d[i].append(j)
    #print(d)
    keys = sorted(d.keys())
    #print(keys)
    pk = 0
    ans = 1
    prev = None
    for i in keys:
        pos = bisect.bisect_left(d[i],pk)
        if pos==len(d[i]):
            pos = 0
            ans+=1
        pos = d[i][pos]
        pk = pos
        #print(pk)
    print(ans)