There's an array A consisting of N non-zero integers A1..N. A subarray of A is called alternating if any two adjacent elements in it have different signs (i.e. one of them should be negative and the other should be positive).

For each x from 1 to N, compute the length of the longest alternating subarray that starts at x - that is, a subarray Ax..y for the maximum possible y ≥ x. The length of such a subarray is y-x+1.

-----Input-----
- The first line of the input contains an integer T - the number of test cases.
- The first line of each test case contains N.
- The following line contains N space-separated integers A1..N.

-----Output-----
For each test case, output one line with N space-separated integers - the lengths of the longest alternating subarray starting at x, for each x from 1 to N.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- -109 ≤ Ai ≤ 109

-----Example-----
Input:
3
4
1 2 3 4
4
1 -5 1 -5
6
-5 -1 -1 2 -2 -3

Output:
1 1 1 1
4 3 2 1
1 1 3 2 1 1

-----Explanation-----
Example case 1. No two elements have different signs, so any alternating subarray may only consist of a single number.
Example case 2. Every subarray is alternating.
Example case 3. The only alternating subarray of length 3 is A3..5.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
test = int(input())
for i in range(test):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * (n + 2)
	b[n - 1] = 1
	for i in range(n - 2, -1, -1):
		if a[i] * a[i + 1] < 0:
			b[i] = b[i + 1] + 1
		else:
			b[i] = 1
	for i in range(n):
		print(b[i], end=' ')
	print()


def f(x, y):
	if x < 0 and y > 0:
		return 1
	elif x > 0 and y < 0:
		return 1
	else:
		return 0
for _ in range(eval(input())):
	n = eval(input())
	c = 1
	b = []
	a = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	for i in range(n - 1):
		if a[i] * a[i + 1] < 0:
			c += 1
		else:
			for j in range(c):
				b.append(c - j)
			c = 1
	for j in range(c):
		b.append(c - j)
	print(' '.join(map(str, b)))


def g(n):
	s = list(map(int, input().split()))
	count = 1
	l = []
	i = 0
	iter = 0
	while i < n:
		count = 1
		for j in range(i + 1, n):
			if s[j] * s[j - 1] < 0:
				count += 1
			else:
				break
		while count > 0:
			l.append(count)
			count -= 1
			i += 1
	if len(l) != n:
		l.append(1)
	return ' '.join((str(i) for i in l))
t = int(input())
for i in range(t):
	n = int(input())
	print(g(n))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	temp = 0
	while i < n - 1:
		count = 1
		while i < n - 1 and (a[i + 1] < 0 and a[i] > 0 or (a[i + 1] > 0 and a[i] < 0)):
			count += 1
			i += 1
		while count > 0:
			print(count, end=' ')
			temp += 1
			count -= 1
		i += 1
	if temp != n:
		print(1)
	else:
		print('')


tc = int(input())
for _ in range(tc):
	n = int(input())
	arr = list(map(int, input().split()))
	st = 0
	en = st + 1
	res = []
	while st < n:
		while True:
			if en == n:
				break
			if arr[en - 1] > 0 and arr[en] < 0:
				en += 1
				continue
			if arr[en - 1] < 0 and arr[en] > 0:
				en += 1
				continue
			break
		for i in range(st, en):
			res.append(en - i)
		st = en
		en = en + 1
	print(' '.join(map(str, res)))


for _ in range(eval(input())):
	n = eval(input())
	a = list(map(int, input().split()))
	b = [1] * n
	for i in range(n - 2, -1, -1):
		if a[i + 1] < 0 and a[i] > 0 or (a[i + 1] > 0 and a[i] < 0):
			b[i] = b[i] + b[i + 1]
	for i in range(n):
		print(b[i], end=' ')
	print()


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().strip().split(' ')))
	a = a[::-1]
	arr = [1]
	for i in range(1, n):
		if a[i - 1] < 0 and a[i] >= 0 or (a[i - 1] >= 0 and a[i] < 0):
			arr.append(1 + arr[i - 1])
		else:
			arr.append(1)
	print(' '.join((str(i) for i in arr[::-1])))


import sys

def altmem(a, b):
	if a < 0 and b >= 0:
		return True
	if a >= 0 and b < 0:
		return True
	return False
for __ in range(eval(input())):
	n = eval(input())
	lists = list(map(int, sys.stdin.readline().split()))
	dp = [0] * 100010
	dp[n - 1] = 1
	for i in range(n - 2, -1, -1):
		dp[i] = dp[i + 1] + 1 if altmem(lists[i], lists[i + 1]) else 1
	print(' '.join((str(i) for i in dp[:n])))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	prev = 0
	end = 0
	arr.append(0)
	for i in range(n):
		if i >= end:
			prev = 1
		else:
			prev -= 1
			print(prev, end=' ')
			continue
		for j in range(i, n):
			if arr[j] * arr[j + 1] < 0:
				prev += 1
			else:
				break
		end = j
		print(prev, end=' ')
	print()


for t in range(int(input())):
	l = []
	n = int(input())
	for x in input().split():
		l.append(int(x))
	i = 0
	res = [0] * n
	while i < n:
		j = i + 1
		while j < n:
			if l[j - 1] * l[j] > 0:
				break
			j += 1
		curr = j - i
		for k in range(i, j):
			res[k] = curr
			curr -= 1
		i = j
	for num in res:
		print(num, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [1] * n
	for i in range(n - 2, -1, -1):
		if arr[i] * arr[i + 1] < 0:
			ans[i] = ans[i + 1] + 1
		else:
			ans[i] = 1
	for __ in ans:
		print(__, end=' ')
	print('')


t = int(input())
for tt in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [1] * n
	for i in range(n - 2, -1, -1):
		if arr[i] < 0 and arr[i + 1] > 0 or (arr[i] > 0 and arr[i + 1] < 0):
			ans[i] = ans[i + 1] + 1
	print(' '.join(map(str, ans)))


t = int(input())
for _ in range(0, t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [1 for _ in range(0, n)]
	for i in range(n - 2, -1, -1):
		if arr[i] * arr[i + 1] < 0:
			ans[i] = ans[i + 1] + 1
	for i in range(0, n):
		print(str(ans[i]) + ' ', end='')
	print('')