Problem: Very soon, the new cell phone services provider "BerLine" will begin its work in Berland!

The start of customer service is planned along the main street of the capital. There are n base stations that are already installed. They are located one after another along the main street in the order from the 1-st to the n-th from left to right. 

Currently, all these base stations are turned off. They will be turned on one by one, one base station per day, according to some permutation p = [p_1, p_2, ..., p_n] ( 1 ≤ p_i ≤ n), where p_i is the index of a base station that will be turned on on the i-th day. Thus, it will take n days to turn on all base stations.

Each base station is characterized by its operating frequency f_i — an integer between 1 and 24, inclusive.

There is an important requirement for operating frequencies of base stations. Consider an arbitrary moment in time. For any phone owner, if we consider all base stations turned on in the access area of their phone, then in this set of base stations there should be at least one whose operating frequency is unique among the frequencies of these stations. Since the power of the phone and the position are not known in advance, this means that for any nonempty subsegment of turned on base stations, at least one of them has to have the operating frequency that is unique among the stations of this subsegment.

For example, let's take a look at a case of n = 7, all n stations are turned on, and their frequencies are equal to f = [1, 2, 1, 3, 1, 2, 1]. Consider any subsegment of the base stations — there is a base station with a unique frequency within this subsegment. However, if f = [1, 2, 1, 2, 3, 2, 1], then there is no unique frequency on the segment [1, 2, 1, 2] from the index 1 to the index 4, inclusive.

Your task is to assign a frequency from 1 to 24 to each of n base stations in such a way that the frequency requirement is met at every moment. Remember that the base stations are turned on in the order of the given permutation p.

Input

The first line of the input contains an integer t (1 ≤ t ≤ 50) — the number of test cases in the input. Then t test case descriptions follow.

The first line of a test case contains an integer n ( 1 ≤ n ≤ 8 500) — the number of "BerLine" base stations.

The following line contains n distinct integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n) — the order in which the base stations are turned on, i. e. on the i-th day the base station with the index p_i is turned on.

It is guaranteed that a correct answer exists for all test cases in the input.

Output

Print exactly t lines, where the j-th line contains the answer for the j-th test case in the input. Print the required frequencies f_1, f_2, ..., f_n (1 ≤ f_i ≤ 24). If there are several possible answers, print any of them.

Example

Input


5
3
1 3 2
3
1 2 3
1
1
10
6 10 4 2 7 9 5 8 3 1
10
2 4 6 9 1 8 10 5 3 7


Output


1 3 2 
10 20 10
1 
2 3 4 5 3 1 3 5 4 2 
1 2 3 4 5 6 7 8 9 10

Note

In the first test case n = 3 and p = [1, 3, 2]. The base stations can be assigned frequencies [1, 3, 2].

  * Day 1: only the base station 1 is turned on, its frequency is 1. 
  * Day 2: the base stations 1 and 3 are turned on, their frequencies are [1, 2]. 
  * Day 3: all base stations are turned on, their frequencies are [1, 3, 2] (in the direction along the street). 



On each day, each nonempty subsegment of turned on base stations has a base station with a unique frequency among this subsegment. It can be shown that three distinct frequencies are necessary in this test case.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long double PI = 4 * atan((long double)1);
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
namespace input {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(long double& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = cd(a, b);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = (0); i < ((int)a.size()); ++i) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = (0); i < (SZ); ++i) re(a[i]);
}
}  // namespace input
using namespace input;
namespace output {
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template <class T>
void pr(const complex<T>& x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
void pc() { pr("]\n"); }
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
}  // namespace output
using namespace output;
namespace io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  cin.sync_with_stdio(0);
  cin.tie(0);
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace io
using namespace io;
typedef decay<decltype(MOD)>::type T;
struct mi {
  T val;
  explicit operator T() const { return val; }
  mi() { val = 0; }
  mi(const long long& v) {
    val = (-MOD <= v && v <= MOD) ? v : v % MOD;
    if (val < 0) val += MOD;
  }
  friend void pr(const mi& a) { pr(a.val); }
  friend void re(mi& a) {
    long long x;
    re(x);
    a = mi(x);
  }
  friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
  mi operator-() const { return mi(-val); }
  mi& operator+=(const mi& m) {
    if ((val += m.val) >= MOD) val -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((val -= m.val) < 0) val += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    val = (long long)val * m.val % MOD;
    return *this;
  }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a != 0);
    return pow(a, MOD - 2);
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
int t;
int n;
void solve() {
  re(n);
  vector<int> p(n);
  re(p);
  reverse(begin(p), end(p));
  vector<int> ans(n + 1);
  int cnt = 0;
  while ((int)p.size()) {
    cnt++;
    set<int> bad, lef;
    lef.insert(0), lef.insert(n + 1);
    for (auto& t : p) lef.insert(t);
    vector<int> P;
    for (auto& t : p) {
      if (!bad.count(t)) {
        ans[t] = cnt;
        auto it = lef.find(t);
        bad.insert(*prev(it));
        bad.insert(*next(it));
      } else {
        P.push_back(t);
      }
      lef.erase(t);
    }
    swap(p, P);
  }
  for (int i = (1); i < (n + 1); ++i) cout << ans[i] << " ";
  cout << "\n";
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  re(t);
  for (int i = (0); i < (t); ++i) solve();
}