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