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: interview

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]))


# ALTARAY.py

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("")