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.io.*;
import java.util.*;

public class Today2 {
	private static boolean dp[][];
	private final static int MAX = 400;
	private final static int LARGE = 100000000;
	private static int ans;

	public static void main(String args[]) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(new BufferedOutputStream(System.out));
		sieve();
		int tt = 1;
		tt = nextInt();
		for (int test = 1; test <= tt; ++test)
			solve();
		out.close();
	}

	static boolean arraySortedOrNot(int a[], int n) {
		if (n == 1 || n == 0)
			return true;
		if (a[n - 1] < a[n - 2])
			return false;
		return arraySortedOrNot(a, n - 1);
	}

	static void swap(long a[], int i, int j) {
		long temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	static long binaryExpo(long a, long b) {
		if (a == 1)
			return 1;
		long res = 1;
		a = a % mod;
		while (b != 0) {
			if ((b & 1) != 0) {
				res = (res % mod * a % mod) % mod;
			}
			a = (a % mod * a % mod) % mod;
			b >>= 1;
		}
		return res;
	}

	private static void solve() throws IOException {
		int n = nextInt();
		int[] arr = new int[n + 1], ans = new int[n + 1], pos = new int[n + 1];
		for(int i = 1; i <= n; i++) {
			arr[i] = nextInt();
			pos[arr[i]] = i;
		}
		for(int i = n; i >= 1; i--) {
			int f = pos[i] - 1, b = pos[i] + 1;
			while(f >= 1 && arr[f] < i)
				f--;
			while(b <= n && arr[b] < i)
				b++;
			if(f == 0 && b <= n)
				ans[i] = ans[arr[b]] + 1;
			else if(f > 0 && b > n)
				ans[i] = ans[arr[f]] + 1;
			else if(f > 0 && b <= n)
				ans[i] = Math.max(ans[arr[f]], ans[arr[b]]) + 1;
			else
				ans[i] = 0;
		}
		for(int i = 1; i <= n; i++) {
			out.print(ans[arr[i]]);
			out.print(' ');
		}
		out.println();
	}

	private static void solve(int n, int a[], int suff[][]) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j <= MAX; j++)
				if (i == 0) {
					if (j != 0)
						suff[i][j] = LARGE;
				} else {
					suff[i][j] = suff[i - 1][j];
					int temp;
					if (j - a[n - i] >= 0)
						temp = suff[i - 1][j - a[n - i]] + 1;
					else
						temp = LARGE;
					if (temp < suff[i][j])
						suff[i][j] = temp;
				}
	}

	static class Pair implements Comparable<Pair> {
		long first, second;

		Pair(long a, long b) {
			first = a;
			second = b;
		}

		public int compareTo(Pair p) {
			return (int) (this.first - p.first);
		}

		public boolean equals(Object p) {
			Pair p1 = (Pair) p;
			return (first == p1.first && second == p1.second);
		}

		public String toString() {
			return this.first + " " + this.second;
		}

		public int hashCode() {
			return (int) ((1l * (inf + 1) * this.first + this.second) % mod);
		}
	}

	static boolean isPerfectSquare(long x) {
		double sr = Math.sqrt(x);
		return ((sr - Math.floor(sr)) == 0);
	}

	private static void solve(int a[], int n, int x, int y, int suff[][], int i) {
		for (int j = i; j >= 1; j--)
			solve(a, i, j);

		for (int sum = x; sum <= y; sum++)
			solve(sum, i, suff, n);
	}

	static long isPowerOfTwo(long n) {
		if (n == 0)
			return -1;
		long count = 0;

		while (n != 1) {
			++count;
			if (n % 2 != 0)
				return -1;
			n = n / 2;
		}
		return count;
	}

	static final long mod = (long) (1e9 + 7);
	static final int inf = (int) (1e9 + 1);

	public static int lowerBound(int[] array, int length, int value) {
		int low = 0;
		int high = length;
		while (low < high) {
			final int mid = (low + high) / 2;
			if (value <= array[mid]) {
				high = mid;
			} else {
				low = mid + 1;
			}
		}
		return low;
	}

	public static int upperBound(int[] array, int length, int value) {
		int low = 0;
		int high = length;
		while (low < high) {
			final int mid = (low + high) / 2;
			if (value >= array[mid]) {
				low = mid + 1;
			} else {
				high = mid;
			}
		}
		return low;
	}

	static int gcd(int a, int b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	private static void solve(int a[], int i, int j) {
		for (int sum = a[i]; sum <= MAX; sum++)
			dp[j][sum] = dp[j - 1][sum - a[i]] || dp[j][sum];
	}

	static BufferedReader br;
	static StringTokenizer st;
	static PrintWriter out;

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

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

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

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

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

	static int[] nextIntArray(int n) {
		int a[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	private static void solve(int sum, int i, int suff[][], int n) {
		for (int j = 0; j <= sum; j++)
			solve(i, j, n, suff, sum);
	}

	private static void solve(int i, int j, int n, int suff[][], int sum) {
		if ((i - suff[n - i - 1][j] >= 0) && dp[i - suff[n - i - 1][j]][sum - j] && suff[n - i - 1][j] < ans)
			ans = suff[n - i - 1][j];
	}

	private static void solve(int ans) {
		if (ans == LARGE)
			out.println(-1);
		else
			out.println(ans);
	}

	static long[] nextLongArray(int n) {
		long a[] = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextLong();
		}
		return a;
	}

	static int[] memset(int n, int val) {
		int ar[] = new int[n];
		Arrays.fill(ar, val);
		return ar;
	}

	static void debug(Object... a) {
		System.out.print("> ");
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}

	static void debug(int a[]) {
		debugnsp(Arrays.stream(a).boxed().toArray());
	}

	static void debug(long a[]) {
		debugnsp(Arrays.stream(a).boxed().toArray());
	}

	static void debugnsp(Object a[]) {
		System.out.print("> ");
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}

	static class UnionFind {
		int[] parents;
		int count;

		UnionFind(int n) {
			parents = new int[n];
			for (int i = 0; i < n; ++i)
				parents[i] = i;
			count = n;
		}

		int find(int i) {
			if (parents[i] == i)
				return i;
			return parents[i] = find(parents[i]);
		}

		void union(int i, int j) {
			int a = find(i);
			int b = find(j);
			if (a != b) {
				parents[a] = b;
				--count;
			}
		}
	}

	static final int MAXN = 100001;
	static int spf[] = new int[MAXN];

	static void sieve() {
		spf[1] = 1;
		for (int i = 2; i < MAXN; i++)
			spf[i] = i;
		for (int i = 4; i < MAXN; i += 2)
			spf[i] = 2;

		for (int i = 3; i * i < MAXN; i++) {
			if (spf[i] == i) {
				for (int j = i * i; j < MAXN; j += i)
					if (spf[j] == j)
						spf[j] = i;
			}
		}
	}
}

/*
 * Jai Sita Ram Ji
 *
 * @author: Nishchal Siddharth Pandey
 */