Nguồn: Free Contest

Bảo Bay Bổng đang trong tiết học thể dục. Thầy giáo bảo cả lớp xếp thành một hàng ngang. Lớp học của Bảo Bay Bổng 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 ~h_i~.

Hai học sinh ~i~ và ~j~ có thể nhìn thấy nhau nếu như ở giữa họ không có học sinh nào có chiều cao lớn hơn. Cụ thể hơn, học sinh ~i~ và ~j~ ~(i < j)~ nhìn thấy nhau nếu như ~h_k \le h_i~ và ~h_k \le h_j~ ~(\forall \; i < k < j)~. Bảo Bay Bổng muốn biết với mỗi học sinh, người đó có thể nhìn thấy bao nhiêu học sinh khác mà 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ố truy vấn.
• Mỗi truy vấn gồm hai dòng, dòng thứ nhất chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa n số nguyên dương ~h_1, h_2, . . . , h_n~ ~(1 \le h_i \le 10^9)~.

Output

• Với mỗi truy vấn, in ra trên một dòng ~n~ số nguyên cách nhau bởi dấu cách là câu trả lời cho truy vấn đó.

Samples

Sample Input 1

1
5
1 2 2 3 2

Sample Output 1

0 1 1 0 0

Clarification

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

Scoring

• Subtask ~1~ (~40\%~ số test): ~n \le 1000~.
• Subtask ~2~ (~60\%~ số test): Không có ràng buộc gì thêm.