You are given an integer array $A$ consisting of $N$ elements. For each element, you are required to find the length of the valley that is defined as:

Let $i$ be the current index and $l$ and $r$ be the leftmost and rightmost index satisfying this property $a[l]>a[l+1].....>a[i-1]>a[i]<a[i+1]<... a[r-1]<a[r]$, then $(r-l+1)$ is the length of the valley. Also, assume that if $A$ is $[7,2,1,5,7,9]$, then the answer is $[1,2,6,3,2,1]$.

Explanation

• A₁ (7): The answer is 1 because there is no element to the left and in right 2 is smaller than 7.
• A₂ (2): A₁>A₂, therefore, the answer is 2
• A₃ (1): A₁>A₂>A₃<A₄<A₅<A₆, therefore, the answer is 6
• A₄ (5): A₄<A₅<A₆, therefore, the answer is 3
• A₅ (7): A₅<A₆, therefore, the answer is 2
• A₆ (9): 7 is smaller than 9 and there is no element to the right, therefore, the answer is 1

Input format

• The first line contains an integer $T$ denoting the number of test cases. 
• The first line of each test case contains an integer $N$ denoting the number of elements in array $A$.
• The second line of each test case contains $N$ space-separated integers of array $A$.

Output format

Print $T$ lines. For each test case, print $N$ space-separated integers denoting the length of the valley for each index.

Constraints

$1 \leq T \leq 20000$

$1 \leq N \leq 500000$

$1 \leq A_i \leq 10^9$

Sum of $N$ over all test cases does not exceed 1000000