Đoạn xen kẽ dài nhất

Cho dãy số nguyên khác \(0\) gồm \(N\) phần tử \(a_1, a_2, \dots, a_N\). Ta gọi một đoạn liên tiếp \(a_i, a_{i+1}, \dots, a_j\) là xen kẽ dấu nếu bất kỳ hai phần tử đứng cạnh nhau trong đoạn đều khác dấu (một số âm, một số dương). Đoạn chỉ có một phần tử luôn được coi là xen kẽ dấu.

Với mỗi vị trí \(i\) (\(1 \le i \le N\)), hãy tìm độ dài của đoạn xen kẽ dấu dài nhất bắt đầu tại vị trí \(i\).

Input

• Dòng đầu tiên chứa số nguyên \(T\) là số bộ test.
• Với mỗi bộ test gồm hai dòng:
• Dòng thứ nhất chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\).

Output

Với mỗi bộ test in ra một dòng gồm \(N\) số nguyên cách nhau bởi dấu cách, số thứ \(i\) là độ dài đoạn xen kẽ dấu dài nhất bắt đầu tại vị trí \(i\).

Constraints

• \(1 \le T \le 10\)
• \(1 \le N \le 10^6\), tổng các giá trị \(N\) trong một file input không vượt quá \(2 \cdot 10^6\)
• \(1 \le |a_i| \le 10^9\)

Sample Input

2
6
3 -2 -5 4 1 -7
5
1 -1 1 -1 1

Sample Output

2 1 2 1 2 1
5 4 3 2 1

Explanation

Ở bộ test thứ nhất: từ vị trí \(1\) đoạn \((3, -2)\) xen kẽ dấu nhưng \(-2, -5\) cùng dấu nên dừng, độ dài \(2\). Từ vị trí \(3\) đoạn \((-5, 4)\) có độ dài \(2\) vì \(4, 1\) cùng dấu. Từ vị trí \(5\) đoạn \((1, -7)\) có độ dài \(2\). Các vị trí còn lại đều cho độ dài \(1\).

Ở bộ test thứ hai toàn bộ dãy xen kẽ dấu nên đáp án là \(5, 4, 3, 2, 1\).