Reign

Statement

For each day i, define reign[i] as the length of the longest contiguous subarray price[l..r] such that l ≤ i ≤ r and price[i] is the strict maximum of price[l..r] — that is, price[j] < price[i] for every j in [l, r] with j ≠ i.

If no such extension exists, the subarray is simply {i} itself and reign[i] = 1.

Output reign[i] for every 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]. Prices may repeat.

Output

For each test case, print a single line containing n space-separated integers reign[0] … reign[n-1].

Constraints

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

Example

2
7
3 1 4 1 5 9 2
5
2 2 2 2 2

2 1 4 1 5 7 1
1 1 1 1 1