Stock Span

Statement

You are given the daily closing prices of a stock for n consecutive days. For each day i, compute the span — the number of consecutive days ending at day i (including day i itself) on which the price was less than or equal to the price on day i.

Formally, the span on day i is the largest integer k such that price[i-k+1], price[i-k+2], …, price[i] are all ≤ price[i].

Input

• The first line contains an integer T — the number of test cases.
• For each test case:
  • A line with a single integer n.
  • A line with n space-separated integers price[0] … price[n-1].

Output

For each test case, print a single line containing n space-separated integers: the span for each day in order.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ n ≤ 105
• 0 ≤ price[i] ≤ 105

Example

3
7
100 80 60 70 60 75 85
5
1 2 3 4 5
1
42

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