Problem: A permutation — is a sequence of length n integers from 1 to n, in which all the numbers occur exactly once. For example, [1], [3, 5, 2, 1, 4], [1, 3, 2] — permutations, and [2, 3, 2], [4, 3, 1], [0] — no.

Polycarp was recently gifted a permutation a[1 ... n] of length n. Polycarp likes trees more than permutations, so he wants to transform permutation a into a rooted binary tree. He transforms an array of different integers into a tree as follows: 

  * the maximum element of the array becomes the root of the tree; 
  * all elements to the left of the maximum — form a left subtree (which is built according to the same rules but applied to the left part of the array), but if there are no elements to the left of the maximum, then the root has no left child; 
  * all elements to the right of the maximum — form a right subtree (which is built according to the same rules but applied to the right side of the array), but if there are no elements to the right of the maximum, then the root has no right child. 



For example, if he builds a tree by permutation a=[3, 5, 2, 1, 4], then the root will be the element a_2=5, and the left subtree will be the tree that will be built for the subarray a[1 ... 1] = [3], and the right one — for the subarray a[3 ... 5] = [2, 1, 4]. As a result, the following tree will be built: 

<image> The tree corresponding to the permutation a=[3, 5, 2, 1, 4].

Another example: let the permutation be a=[1, 3, 2, 7, 5, 6, 4]. In this case, the tree looks like this: 

<image> The tree corresponding to the permutation a=[1, 3, 2, 7, 5, 6, 4].

Let us denote by d_v the depth of the vertex a_v, that is, the number of edges on the path from the root to the vertex numbered a_v. Note that the root depth is zero. Given the permutation a, for each vertex, find the value of d_v.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

The first line of each test case contains an integer n (1 ≤ n ≤ 100) — the length of the permutation.

This is followed by n numbers a_1, a_2, …, a_n — permutation a.

Output

For each test case, output n values — d_1, d_2, …, d_n.

Example

Input


3
5
3 5 2 1 4
1
1
4
4 3 1 2


Output


1 0 2 3 1 
0 
0 1 3 2 

Solution (in JAVA):

Solution:
import java.util.*;
// import java.lang.*;
import java.io.*;

//           THIS TEMPLATE MADE BY AKSH BANSAL.

public class Solution {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args) throws IOException {
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        // ________________________________

        int t = sc.nextInt();
        StringBuilder output = new StringBuilder();

        while (t-- > 0) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for(int i=0;i<n;i++){
                arr[i] = sc.nextInt();
            }
            solver(n,arr, out);
            out.println();
        }

        out.println(output);
        // _______________________________

        // int n = sc.nextInt();
        // out.println(solver());
        // ________________________________
        out.flush();
    }
    private static int[] st;
    public static void solver(int len, int[] arr, PrintWriter out) {
        // map<value,depth>
        Map<Integer, Integer> map = new HashMap<>();
        int[] getIndex = new int[len+1];
        for(int i=0;i<len;i++){
            getIndex[arr[i]] = i;
        }
        st = constructST(arr,len);
        helper(0,len-1, getIndex, map,0,len, arr);
        
        for(int i=0;i<len;i++){
            out.print(map.get(arr[i])+" ");
        }

    }

    private static void helper(
        int start, int end, int[] getIndex, 
        Map<Integer,Integer> map, int depth,
        int len, int[] arr
    ){
        if(start>end)return;
        if(start==end){
            map.put(arr[start],depth);
            return;
        }
        int max = getMax(st,len,start,end);
        // System.out.println(depth+"__"+ max+"_idx: "+getIndex[max]);

        map.put(max,depth);

        helper(start,getIndex[max]-1,getIndex,map,depth+1,len, arr);
        helper(getIndex[max]+1,end,getIndex,map,depth+1,len, arr);
    }

    // A utility function to get the
    // middle index of given range.
    static int getMid(int s, int e)
    {
        return s + (e - s) / 2;
    }
 
    /*
    * A recursive function to get the sum
    of values in given range of the array.
    * The following are parameters 
      for this function.
    *
    * st -> Pointer to segment tree
    * node -> Index of current node in
    *         the segment tree.
    * ss & se -> Starting and ending indexes
    *         of the segment represented
    *         by current node, i.e., st[node]
    * l & r -> Starting and ending indexes
    *         of range query
    */
    static int MaxUtil(int[] st, int ss, 
                       int se, int l,
                       int r, int node)
    {
 
        // If segment of this node is completely
        // part of given range, then return
        // the max of segment
        if (l <= ss && r >= se)
            return st[node];
 
        // If segment of this node does not
        // belong to given range
        if (se < l || ss > r)
            return -1;
 
        // If segment of this node is partially
        // the part of given range
        int mid = getMid(ss, se);
 
        return Math.max(
            MaxUtil(st, ss, mid, l, r,
                     2 * node + 1),
            MaxUtil(st, mid + 1, se, l, r,
                    2 * node + 2));
    }
 
    /*
    * A recursive function to update the
    nodes which have the given index in their
    * range. The following are parameters
    st, ss and se are same as defined above
    * index -> index of the element to be updated.
    */
    static void updateValue(int arr[], int[] 
                            st, int ss,
                            int se, int index, 
                            int value,
                            int node)
    {
        if (index < ss || index > se) {
            System.out.println("Invalid Input");
            return;
        }
 
        if (ss == se) {
 
            // update value in array and in
            // segment tree
            arr[index] = value;
            st[node] = value;
        }
        else {
            int mid = getMid(ss, se);
 
            if (index >= ss && index <= mid)
                updateValue(arr, st, ss, mid, 
                            index, value,
                            2 * node + 1);
            else
                updateValue(arr, st, mid + 1, se, index,
                            value, 2 * node + 2);
 
            st[node] = Math.max(st[2 * node + 1],
                                st[2 * node + 2]);
        }
        return;
    }
 
    // Return max of elements in range from
    // index l (query start) to r (query end).
    static int getMax(int[] st, int n, int l, int r)
    {
 
        // Check for erroneous input values
        if (l < 0 || r > n - 1 || l > r) {
            System.out.printf("Invalid Input\n");
            return -1;
        }
 
        return MaxUtil(st, 0, n - 1, l, r, 0);
    }
 
    // A recursive function that constructs Segment
    // Tree for array[ss..se]. si is index of
    // current node in segment tree st
    static int constructSTUtil(int arr[],
                               int ss, int se,
                               int[] st, int si)
    {
 
        // If there is one element in array, store
        // it in current node of segment tree and return
        if (ss == se) {
            st[si] = arr[ss];
            return arr[ss];
        }
 
        // If there are more than one elements, then
        // recur for left and right subtrees and
        // store the max of values in this node
        int mid = getMid(ss, se);
 
        st[si] = Math.max(
            constructSTUtil(arr, ss, mid,
                            st, si * 2 + 1),
            constructSTUtil(arr, mid + 1,
                            se, st,
                            si * 2 + 2));
 
        return st[si];
    }
 
    /*
    * Function to construct segment tree from
    given array. This function allocates
    * memory for segment tree.
    */
    static int[] constructST(int arr[], int n)
    {
 
        // Height of segment tree
        int x = (int)Math.ceil(Math.log(n) / Math.log(2));
 
        // Maximum size of segment tree
        int max_size = 2 * (int)Math.pow(2, x) - 1;
 
        // Allocate memory
        int[] st = new int[max_size];
 
        // Fill the allocated memory st
        constructSTUtil(arr, 0, n - 1, st, 0);
 
        // Return the constructed segment tree
        return st;
    }
}