Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

On a sunny day, Akbar and Birbal were taking a leisurely walk in palace gardens. Suddenly, Akbar noticed a bunch of sticks on the ground and decided to test Birbal's wits.

There are $N$ stick holders with negligible size (numbered $1$ through $N$) in a row on the ground. Akbar places all the sticks in them vertically; for each valid $i$, the initial height of the stick in the $i$-th holder is $A_{i}$. Birbal has a stick cutter and his task is to completely cut all these sticks, i.e. reduce the heights of all sticks to $0$. He may perform zero or more operations; in each operation, he should do the following:
Choose an integer $H$ and fix the cutter at the height $H$ above the ground.
The cutter moves from the $1$-st to the $N$-th stick holder. Whenever it encounters a stick whose current height is greater than $H$, it cuts this stick down to height $H$ (i.e. for a stick with height $h > H$, it removes its upper part with length $h-H$).
All the upper parts of sticks that are cut in one operation must have equal lengths. Otherwise, the operation may not be performed.

For example, if the heights of sticks are initially $[5, 3, 5]$, then some valid values for $H$ in the first operation are $3$ and $4$ ― the cutter cuts the upper parts of two sticks and their lengths are $[2, 2]$ and $[1, 1]$ respectively. $H = 2$ is an invalid choice because it would cut the upper parts of all three sticks with lengths $[3, 1, 3]$, which are not all equal.

Akbar wants Birbal to completely cut all sticks in the minimum possible number of operations. If you want to be friends with Birbal, help him solve the problem.

------  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 number of operations needed to completely cut all the sticks.

------  Constraints ------
$1 ≤ T ≤ 50$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{9}$ for each valid $i$

------  Subtasks ------
Subtask #1 (20 points): $N ≤ 50$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
1

3

1 2 3
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
Example case 1: Birbal may perform the following three operations:
- Fix the cutter at $H = 2$. The heights of the sticks after this operation are $[1, 2, 2]$.
- Fix the cutter at $H = 1$. The heights of the sticks after this operation are $[1, 1, 1]$.
- Fix the cutter at $H = 0$. After this operation, all sticks are completely cut.

Source: codechef | Difficulty: EASY
Tags: Data structures

Implementation


Solutions:
for _ in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	if sum(l) == 0:
		print(0)
	else:
		sl = set(l)
		c = len(sl)
		for x in sl:
			if x == 0:
				c = c - 1
		print(c)


for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	seta = set((x for x in set(a) if x != 0))
	print(len(seta))


t = int(input())
for i in range(t):
	n = int(input())
	sticks = set(map(int, input().split()))
	output = len(sticks)
	if 0 in sticks:
		print(output - 1)
	else:
		print(output)


for _ in range(int(input())):
	input()
	a = set(map(int, input().split()))
	print(len(a) if min(a) else len(a) - 1)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	if sum(A) != 0:
		A.sort()
		(m, c) = (0, 0)
		for i in A:
			if m < i:
				m = i
				c += 1
		print(c)
	else:
		print(0)


for _ in range(int(input())):
	__ = input()
	sticks = set(map(int, input().split()))
	output = len(sticks)
	if 0 in sticks:
		print(output - 1)
	else:
		print(output)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) != 0:
		a.sort()
		(m, c) = (0, 0)
		for i in a:
			if m < i:
				m = i
				c += 1
		print(c)
	else:
		print(0)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	b.sort()
	c = 0
	max = 0
	for k in range(0, a):
		if b[k] > max:
			c += 1
			max = b[k]
	print(c)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	(a, b) = (0, 0)
	for i in arr:
		if a < i:
			a = i
			b += 1
	print(b)
	t -= 1


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = Counter(l).values()
	ans = []
	for i in c:
		ans.append(i)
	z = len(ans)
	if 0 in l:
		print(z - 1)
	else:
		print(z)


test = int(input())
for i in range(test):
	count = 0
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	for i in range(1, n):
		if arr[i] == arr[i - 1]:
			count += 1
	if arr[0] == 0:
		print(n - count - 1)
	else:
		print(n - count)


for i in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	L = [x for x in L if x != 0]
	print(len(set(L)))


for z in range(int(input())):
	n = int(input())
	unique = set(list(map(int, input().split())))
	if 0 in unique:
		print(len(unique) - 1)
	else:
		print(len(unique))


for i in range(int(input())):
	a = int(input())
	b = set(map(int, input().split()))
	if 0 in b:
		print(len(b) - 1)
	else:
		print(len(b))


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	d = {}
	for i in nums:
		if i != 0:
			d[i] = True
	print(len(d))


for _ in range(int(input())):
	n = int(input())
	nums = set(map(int, input().split()))
	print(len(nums) - (0 in nums))


for i in range(int(input())):
	n = int(input())
	l = list(set(map(int, input().split())))
	if 0 in l:
		print(len(l) - 1)
	else:
		print(len(l))


n = int(input())
for i in range(n):
	k = int(input())
	z = sorted(list(map(int, input().split())))
	p = 0
	c = 0
	for i in range(k):
		if z[i] > p:
			p = z[i]
			c = c + 1
	print(c)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = sorted(b)
	m = 0
	d = 0
	for j in range(a):
		if c[j] > m:
			m = c[j]
			d += 1
	print(d)


for _ in range(int(input())):
	n = int(input())
	h = sorted(list(map(int, input().split())))
	c = 0
	k = 0
	for i in range(n):
		if h[i] > k:
			k = h[i]
			c = c + 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = sorted(l)
	(c, m) = (0, 0)
	for i in range(n):
		if l[i] > m:
			m = l[i]
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	max = 0
	count = 0
	for i in range(n):
		if a[i] > max:
			max = a[i]
			count += 1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	maxNum = 0
	count = 0
	for i in range(n):
		if arr[i] > maxNum:
			maxNum = arr[i]
			count += 1
	print(count)


from collections import Counter
for i in range(0, int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = Counter(a)
	t = 0
	for i in d:
		if i == 0:
			t = t + 1
			break
		else:
			continue
	if t == 1:
		print(len(d) - 1)
	else:
		print(len(d))


t = int(input())
for i in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	li.sort()
	c = 0
	mx = 0
	for j in li:
		if j > mx:
			c += 1
			mx = j
	print(c)


t = int(input())
for i in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	b.sort()
	max1 = 0
	c = 0
	for i in range(a):
		if b[i] > max1:
			c = c + 1
			max1 = b[i]
	print(c)


for i in range(int(input())):
	N = int(input())
	length_list = [int(s) for s in str(input()).split()]
	length_list = list(set(length_list))
	if 0 in length_list:
		print(len(length_list) - 1)
	else:
		print(len(length_list))


t = int(input())
for _ in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	l = 0
	count = 0
	for i in range(1, len(A)):
		if A[i] == A[l]:
			continue
		l = i
		count += 1
	if A[-1] != 0:
		count += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	ans = 0
	for i in range(1, n):
		if l[i] != l[i - 1]:
			ans += 1
	if l[0] == 0:
		print(ans)
	else:
		print(ans + 1)


T = int(input())
for i in range(T):
	N = int(input())
	A = tuple(map(int, input().split()))
	ai = set(A)
	print(len(ai) + (-1 if 0 in A else 0))


for _ in range(int(input())):
	N = int(input())
	A = tuple(map(int, input().split()))
	distinctA = tuple(set(A))
	print(len(distinctA) + (-1 if 0 in A else 0))


t = int(input())
for i in range(t):
	se = set()
	n = int(input())
	s = list(map(int, input().split()))
	for i in s:
		if i != 0:
			se.add(i)
	print(len(se))


for _ in range(int(input())):
	n = int(input())
	sticks = set(filter(lambda stick: stick != 0, map(int, input().split())))
	print(len(sticks))


testcases = int(input())
for t in range(testcases):
	l = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	count = 0
	maxTree = arr[0]
	if maxTree == 0:
		print(count)
	else:
		for i in range(len(arr)):
			if maxTree > arr[i]:
				count = count + 1
				maxTree = arr[i]
		print(count if maxTree == 0 else count + 1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	max1 = 0
	c = 0
	for i in range(n):
		if l[i] > max1:
			c = c + 1
			max1 = l[i]
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	sticks = list(map(int, input().split()))
	sa = 0
	sticks.sort()
	h = 0
	for j in range(0, n):
		if sticks[j] > h:
			sa = sa + 1
			h = sticks[j]
	print(sa)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	count = 0
	max1 = 0
	for i in range(N):
		if A[i] > max1:
			count += 1
			max1 = A[i]
	print(count)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	if 0 not in s:
		print(len(s))
	else:
		print(len(s) - 1)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	if 0 not in s:
		print(len(s))
	else:
		print(len(s) - 1)


for i in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	g = set(l)
	g.discard(0)
	print(len(g))


T = int(input())
while T >= 1 and T <= 50:
	N = int(input())
	if N >= 1 and N <= 100000:
		li = [int(x) for x in input().split(' ', N) if int(x) >= 0 and int(x) <= 10000000000]
		s = set(li)
		s.discard(0)
		print(len(s))
	T -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	a = set(arr)
	if 0 in a:
		print(len(a) - 1)
	else:
		print(len(a))


import heapq
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = set(l)
	if 0 not in a:
		print(len(a))
	else:
		print(len(a) - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = set(map(int, input().split()))
	c = 0
	for i in a:
		if i > 0:
			c += 1
	print(c)


for _ in range(int(input())):
	I = int(input())
	A = list(map(int, input().split()))
	count = 0
	minn = 0
	A.sort()
	for i in A:
		if i > minn:
			minn = i
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	count = 0
	minn = 0
	lis.sort()
	for i in lis:
		if i > minn:
			minn = i
			count += 1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	stick = map(int, input().split())
	stick_set = set(stick)
	if 0 in stick_set:
		stick_set.remove(0)
	print(len(stick_set))


for i in range(int(input())):
	num = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	o = 0
	for i in range(1, num):
		if arr[i] < arr[i - 1]:
			o += 1
	if arr[num - 1] != 0:
		o += 1
	print(o)