In mathematics, the [degree] of polynomials in one variable is the highest power of the variable in the algebraic expression with non-zero coefficient.

Chef has a polynomial in one variable x with N terms. The polynomial looks like A_{0}\cdot x^{0} + A_{1}\cdot x^{1} + \ldots + A_{N-2}\cdot x^{N-2} + A_{N-1}\cdot x^{N-1} where A_{i-1} denotes the coefficient of the i^{th} term x^{i-1} for all (1≤ i≤ N). 

Find the degree of the polynomial.

Note: It is guaranteed that there exists at least one term with non-zero coefficient.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case contains of a single integer N - the number of terms in the polynomial.
- Second line of each test case contains of N space-separated integers - the i^{th} integer A_{i-1} corresponds to the coefficient of x^{i-1}.

------ Output Format ------ 

For each test case, output in a single line, the degree of the polynomial.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 1000$
$-1000 ≤A_{i} ≤1000$
$A_{i} \ne 0$ for at least one $(0≤i < N)$.

----- Sample Input 1 ------ 
4
1
5
2
-3 3
3
0 0 5
4
1 2 4 0

----- Sample Output 1 ------ 
0
1
2
2
----- explanation 1 ------ 
Test case $1$: There is only one term $x^{0}$ with coefficient $5$. Thus, we are given a constant polynomial and the degree is $0$.

Test case $2$: The polynomial is $-3\cdot x^{0} + 3\cdot x^{1} = -3 + 3\cdot x$. Thus, the highest power of $x$ with non-zero coefficient is $1$.

Test case $3$: The polynomial is $0\cdot x^{0} + 0\cdot x^{1} + 5\cdot x^{2}= 0+0 + 5\cdot x^{2}$. Thus, the highest power of $x$ with non-zero coefficient is $2$.

Test case $4$: The polynomial is $1\cdot x^{0} + 2\cdot x^{1}+ 4\cdot x^{2} + 0\cdot x^{3}= 1 + 2\cdot x + 4\cdot x^{2}$. Thus, the highest power of $x$ with non-zero coefficient is $2$.

Source: codechef | Difficulty: EASY
Tags: Mathematics

Implementation


Solutions:
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	reduce = 0
	for i in range(N):
		if A[-1 - i] == 0:
			reduce += 1
		else:
			break
	print(len(A) - 1 - reduce)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.reverse()
	high = len(a)
	for i in range(len(a)):
		if a[i] == 0:
			high -= 1
		else:
			break
	print(high - 1)


t = int(input())
for i in range(t):
	z = 0
	num = int(input())
	x = list(map(int, input().split()))
	for i in range(num):
		if x[-1 - i] == 0:
			z = z + 1
		else:
			break
	print(len(x) - z - 1)


for sreeja in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	dec = 0
	for i in range(N):
		if A[-1 - i] == 0:
			dec += 1
		else:
			break
	print(len(A) - 1 - dec)


t = int(input())
for i in range(0, t):
	n = int(input())
	c = list(map(int, input().split()))[:n]
	for (i, e) in reversed(list(enumerate(c))):
		if e != 0:
			print(i)
			break


for i in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	j = x - 1
	while j >= 0:
		if y[j] == 0:
			j -= 1
		else:
			print(j)
			break


t = int(input())
for i in range(t):
	z1 = 0
	number = int(input())
	x = list(map(int, input().split()))
	for i in range(number):
		if x[-1 - i] == 0:
			z1 = z1 + 1
		else:
			break
	print(len(x) - z1 - 1)


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


for i in range(int(input())):
	c = 0
	n = int(input())
	l = list(map(int, input().split()))
	for j in range(n):
		if l[-1 - j] == 0:
			c += 1
		else:
			break
	print(len(l) - c - 1)


for _ in range(int(input())):
	N = int(input())
	Cf = list(map(int, input().split()))
	Z = 0
	for i in range(N):
		if Cf[-1 - i] == 0:
			Z += 1
		else:
			break
	print(N - 1 - Z)


t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	z = 0
	for i in range(n):
		if A[-1 - i] == 0:
			z = z + 1
		else:
			break
	print(len(A) - z - 1)


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	for j in range(n):
		if lst[n - j - 1] != 0:
			print(n - j - 1)
			break


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	z = 0
	for i in range(x):
		if l[-1 - i] == 0:
			z += 1
		else:
			break
	print(len(l) - z - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	for i in reversed(range(0, n)):
		if l[i] != 0:
			print(i)
			break


for _ in range(int(input())):
	n = int(input())
	z = 0
	a = list(map(int, input().split()))
	for i in range(n):
		if a[-1 - i] == 0:
			z = z + 1
		else:
			break
	print(len(a) - z - 1)


for t in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	l1 = l[::-1]
	for i in l1:
		if i != 0:
			print(n - 1)
			break
		else:
			n = n - 1


import math
n = int(input())
v = 1
for i in range(n):
	a = int(input())
	m1 = list(map(int, input().split()))
	c = 0
	c1 = 0
	for i in range(a):
		if m1[c] * math.pow(v, i) != 0:
			high = i
		c = c + 1
	print(high)


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	d = 0
	for j in range(n):
		if a[n - j - 1] != '0':
			d = n - j - 1
			break
	print(d)


for _ in range(int(input())):
	N = int(input())
	pows = list(map(int, input().split()))
	coif = []
	for (ind, i) in enumerate(pows):
		if i != 0:
			coif.append(ind)
	print(coif[-1])


t = int(input())
for i in range(t):
	x = int(input())
	l = list(map(int, input().split()))
	if l[-1] != 0:
		print(x - 1)
	else:
		while l[-1] == 0:
			l.pop()
		print(len(l) - 1)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	i = -1
	while True:
		if l[i] == 0:
			i -= 1
		else:
			print(a + i)
			break


for t in range(int(input())):
	terms = int(input())
	c = 0
	ele = list(map(int, input().split()))
	for i in range(terms):
		if ele[-1 - i] == 0:
			c += 1
		else:
			break
	print(len(ele) - c - 1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {i: l[i] for i in range(n)}
	p = {i: j for (i, j) in d.items() if j != 0}
	print(max(p))


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	for (j, e) in reversed(list(enumerate(A))):
		if e != 0:
			print(j)
			break


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


t = int(input())
while t > 0:
	t = t - 1
	a = int(input())
	s = list(input().split())
	for i in range(0, a):
		if s[i] != '0':
			l = i
	print(l)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for (i, j) in enumerate(l):
		if j != 0:
			c = i
	print(c)


T = int(input())
for _ in range(T):
	N = int(input())
	P = [int(i) for i in input().split()][0:N]
	degree = 0
	for i in range(-1, -len(P), -1):
		if P[i] == 0:
			continue
		else:
			degree = len(P) + i
			break
	print(degree)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	hp = 0
	i = len(arr) - 1
	while i >= 0:
		if arr[i] != 0:
			hp = i
			break
		i -= 1
	print(hp)


for k in range(int(input())):
	degree = 0
	t = int(input())
	l = list(map(int, input().split()))
	for i in range(t):
		if l[i] != 0:
			degree = i
	print(degree)


for t in range(int(input())):
	n = int(input())
	a = input()
	l = a.rstrip(' 0')
	lst = l.split()
	print(len(lst) - 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	for j in range(n):
		if l[j] != 0:
			k = j
	print(k)


for _ in range(int(input())):
	a = int(input())
	list1 = list(map(int, input().split()))
	list1 = list(list1)
	index = 0
	for i in range(len(list1) - 1, -1, -1):
		if list1[i] != 0:
			index = i
			break
	print(index)


for t in range(int(input())):
	n = int(input())
	k = list(range(0, n))
	l = []
	s = list(map(int, input().split()))
	for m in range(0, n):
		l.append(s[m] * k[m])
	for j in range(n - 1, -1, -1):
		if l[j] != 0:
			break
	print(k[j])


for _ in range(int(input())):
	n = int(input())
	l = input().split()
	for j in range(n - 1, -1, -1):
		if l[j] != '0':
			print(j)
			break


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	r = n - 1
	for i in a[::-1]:
		if i != 0:
			print(r)
			break
		r -= 1


n = int(input())
for i in range(n):
	m = int(input())
	arr = list(map(int, input().split()))
	b = len(arr)
	z = 0
	for i in range(b):
		if arr[-1 - i] == 0:
			z += 1
		else:
			break
	print(b - z - 1)


def code():
	cases = int(input())
	for _ in range(cases):
		N = int(input())
		coefficents = list(map(int, input().split(' ')))
		cur_max_degree = 0
		for (degree, constant) in enumerate(coefficents):
			if constant != 0 and degree >= cur_max_degree:
				cur_max_degree = degree
		print(cur_max_degree)
code()


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	a = 0
	x = n
	for i in range(0, n):
		if ar[x - 1] != 0:
			a = x - 1
		else:
			x = x - 1
			continue
	print(a)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	for j in range(N):
		if A[j] != 0:
			d = j
	print(d)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	for j in range(n):
		if a[j] != 0:
			c = j
	print(c)


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	while n >= 0:
		if l[n - 1] == 0:
			n = n - 1
		else:
			print(n - 1)
			break
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1, -1, -1):
		if a[i]:
			print(i)
			break


n = int(input())
for i in range(n):
	n1 = int(input())
	a = list(map(int, input().split(' ')))
	while a[-1] == 0:
		a.pop()
	print(len(a) - 1)


n = int(input())
for _ in range(n):
	x = int(input())
	lis = list(map(int, input().split()))
	s1 = 0
	for i in range(x):
		if lis[-1 - i] == 0:
			s1 += 1
		else:
			break
	print(len(lis) - s1 - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	degree = -1
	for i in range(n):
		if a[i] != 0:
			degree = i
	print(degree)