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.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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())
	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())
	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
	return nKeys - count

def __starting_point():
	for _ in range(int(input())):
		n = int(input())
		A = list(map(int, input().split()))
		print(findM(A, n))
__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)


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)


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 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
	INF = int(1000000000.0)
	mod = int(1000000000.0) + 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)


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)
	keys = sorted(d.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(ans)