Cho dãy \(A\) gồm \(N\) số nguyên \(a_1,a_2...a_n\) \((|a_i| \le 10^9)\). Một đoạn con \(a[i..j]\) có độ dài là \(j-i+1\) \((1 \le i \le j \le N)\). Đoạn con được gọi là đoạn xen kẽ nếu hai phần tử bất kỳ nào đứng cạnh nhau đều trái dấu.

Yêu cầu của bài tập này bạn cần viết chương trình thực hiện nhiệm vụ sau: Với mỗi vị trí \(i\) \((1 \le i \le N)\) hãy tính độ dài dãy con xen kẽ dài nhất của dãy \(A\) bắt đầu ở vị trí \(i\).

Dữ liệu vào

• Dòng đầu ghi \(T\) là số lượng bộ test \((1 \le T \le 20)\)
• Trong \(2 \times T\) dòng tiếp theo ghi thông tin về các bộ test: dòng đầu ghi \(N\), dòng hai ghi dãy \(A\) \((1 \le N \le 10^5)\)

Dữ liệu ra

• Gồm \(T\) dòng, mỗi dòng ghi \(N\) số nguyên lần lượt là độ dài dãy con xen kẽ dài nhất tìm được tương ứng với mỗi test trong input.

Input 1

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

Output 1

1 1 3 2 1 1