Tại thành phố HP có n tòa tháp truyền hình, đánh số từ 1 đến n, xếp trên một đường thẳng từ trái qua phải, có chiều cao lần lượt là h₁, h₂, …, hₙ.

Các tháp truyền hình sẽ truyền tín hiệu từ phải qua trái.

Tháp truyền hình A sẽ chắn tín hiệu của tháp truyền hình B nếu:

• Tháp A ở bên trái tháp B;
• Tháp A cao hơn tháp B.

Vậy phạm vi phát tín hiệu của tháp i có thể định nghĩa bằng (số tháp liền kề bên trái có chiều cao nhỏ hơn hoặc bằng hᵢ) và cộng thêm 1.

Yêu cầu: Xác định phạm vi phát tín hiệu của mỗi tháp.

INPUT

• Dòng đầu tiên chứa số nguyên dương t (1 ≤ t ≤ 10) là số test;
• Với mỗi test, dòng tiếp theo chứa số nguyên dương N (2 ≤ N ≤ 10⁶);
• Dòng tiếp theo chứa N số nguyên dương h₁, h₂, …, hₙ (1 ≤ hᵢ ≤ 10⁸).

OUTPUT

Gồm t dòng, mỗi dòng ghi N số nguyên, số thứ i là phạm vi phát tín hiệu của tháp i.

Ví dụ

Sample Input

1
7
100 80 60 70 60 75 85

Sample Output

1 1 1 2 1 4 6