Trong giờ tập trung, Thầy giáo chủ nhiệm yêu cầu cả lớp xếp thành một hàng ngang. Lớp học có ~n~ học sinh, khi xếp thành hàng ngang các học sinh được đánh số từ ~1~ tới ~n~ theo thứ tự từ trái qua phải. Học sinh thứ ~i~ có chiều cao là ~h_i~.

Hai học sinh ~i~ và ~j~ có thể nhìn thấy nhau nếu mọi học sinh đứng giữa họ đều có chiều cao không lớn hơn chiều cao của cả hai học sinh ~i~ và ~j~. Cụ thể, hai học sinh ~i~ và ~j~ ~(i < j)~ nhìn thấy nhau nếu:

• ~h_k \le h_i~;

• ~h_k \le h_j~ với mọi ~k~ thỏa ~i < k < j~.

Yêu cầu: Với mỗi học sinh hãy cho biết học sinh đó có thể nhìn thấy bao nhiêu học sinh khác có cùng chiều cao với họ.

Input

• Dòng đầu tiên chứa số nguyên dương ~q~ ~(1 \le q \le 10)~ — số test;

• Mỗi test gồm hai dòng:

  • Dòng thứ nhất chứa số nguyên dương ~n~ ~(1 \le n \le 100\,000)~;

  • Dòng thứ hai chứa ~n~ số nguyên dương ~h_1, h_2, \dots, h_n~ ~(1 \le h_i \le 10^9; 1 \le i \le n)~.

Output

Ghi ra ~q~ dòng. Dòng thứ ~i~ gồm ~n_i~ số nguyên; số thứ ~j~ là số học sinh có cùng chiều cao mà học sinh thứ ~j~ có thể nhìn thấy trong test thứ ~i~.

Scoring

Sample Input 1

1
5
1 2 2 3 2

Sample Output 1

0 1 1 0 0

Notes

• Học sinh thứ ~2~ có thể nhìn thấy học sinh ~1~, ~3~ và ~4~ nhưng chỉ có học sinh ~3~ có cùng chiều cao với học sinh ~2~.

• Học sinh thứ ~3~ chỉ có thể nhìn thấy học sinh ~2~ mà không thể thấy học sinh ~5~ do có học sinh ~4~ có chiều cao lớn hơn.