Có một dãy đài tín hiệu xếp thành một hàng ngang từ trái qua phải, mỗi đài truyền đi một tín hiệu từ phải qua trái. Đài A sẽ chặn tín hiệu của đài B truyền đi nếu đài A nằm bên trái tòa B và đài A cao hơn đài B. Độ dài dải tìn hiệu của một đài A là được tính bằng số các đài liên tiếp bắt đầu từ đài A, kéo dài sang trái, có đồ cao thấp hơn hoặc bằng đài A + 1. Bạn cần tính dải tín hiệu của tất cả các đài.

Input

Dòng đầu tiên gồm 1 số nguyên t ~(1 \le T \le 10)~, số lượng test.

Mỗi test sẽ gồm 2 dòng :

Dòng đầu tiên gồm 1 số nguyên n ~(2 \le n \le 10^6)~, số lượng đài tín hiệu.

Dòng thứ hai gồm dáy n số nguyên ai ~(1 \le ai \le 10^8)~, độ cao của đài tín hiệu thứ i.

Output

Gồm n số nguyên d1, d2, d3, .. dn, với di là độ dài dải tín hiệu của đài thứ i.

Sample Input

1
7
100 80 60 70 60 75 85

Sample Output

1 1 1 2 1 4 6