Berland Music is a music streaming service built specifically to support Berland local artist. Its developers are currently working on a song recommendation module.

So imagine Monocarp got recommended n songs, numbered from 1 to n. The i-th song had its predicted rating equal to p_i, where 1 ≤ p_i ≤ n and every integer from 1 to n appears exactly once. In other words, p is a permutation.

After listening to each of them, Monocarp pressed either a like or a dislike button. Let his vote sequence be represented with a string s, such that s_i=0 means that he disliked the i-th song, and s_i=1 means that he liked it.

Now the service has to re-evaluate the song ratings in such a way that:

  * the new ratings q_1, q_2, ..., q_n still form a permutation (1 ≤ q_i ≤ n; each integer from 1 to n appears exactly once); 
  * every song that Monocarp liked should have a greater rating than every song that Monocarp disliked (formally, for all i, j such that s_i=1 and s_j=0, q_i>q_j should hold). 



Among all valid permutations q find the one that has the smallest value of ∑_{i=1}^n |p_i-q_i|, where |x| is an absolute value of x.

Print the permutation q_1, q_2, ..., q_n. If there are multiple answers, you can print any of them.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of testcases.

The first line of each testcase contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of songs.

The second line of each testcase contains n integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n) — the permutation of the predicted ratings.

The third line contains a single string s, consisting of n characters. Each character is either a 0 or a 1. 0 means that Monocarp disliked the song, and 1 means that he liked it.

The sum of n over all testcases doesn't exceed 2 ⋅ 10^5.

Output

For each testcase, print a permutation q — the re-evaluated ratings of the songs. If there are multiple answers such that ∑_{i=1}^n |p_i-q_i| is minimum possible, you can print any of them.

Example

Input


3
2
1 2
10
3
3 1 2
111
8
2 3 1 8 5 4 7 6
01110001


Output


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

Note

In the first testcase, there exists only one permutation q such that each liked song is rating higher than each disliked song: song 1 gets rating 2 and song 2 gets rating 1. ∑_{i=1}^n |p_i-q_i|=|1-2|+|2-1|=2.

In the second testcase, Monocarp liked all songs, so all permutations could work. The permutation with the minimum sum of absolute differences is the permutation equal to p. Its cost is 0.
1
7
1 2 3 4 5 6 7
0101010
 3
2
1 2
10
7
1 2 3 4 5 6 7
0101010
8
2 3 1 8 5 4 7 6
01110001
 1
50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
10101010101010101010101010101010101010101010101010

1 5 2 6 3 7 4
 2 1
1 5 2 6 3 7 4
1 6 5 8 3 2 4 7
 26 1 27 2 28 3 29 4 30 5 31 6 32 7 33 8 34 9 35 10 36 11 37 12 38 13 39 14 40 15 41 16 42 17 43 18 44 19 45 20 46 21 47 22 48 23 49 24 50 25

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution{
static long mod=(long)1e9+7;
static FastScanner sc = new FastScanner();
public static void solve(){
  int n=sc.nextInt();
  int[] a=sc.readArray(n);
  String s=sc.next();
  PriorityQueue<Pair> p0=new PriorityQueue<>((a1,b)->a1.val-b.val);
  PriorityQueue<Pair> p1=new PriorityQueue<>((a1,b)->a1.val-b.val);
  for (int i=0;i<n;i++) {
    if (s.charAt(i)=='0') {
      p0.add(new Pair(a[i],i));
    }else{
      p1.add(new Pair(a[i],i));
    }
  }
  int ct=1;
  int[] ans=new int[n];
  while(!p0.isEmpty()){
    Pair p=p0.poll();
    ans[p.ind]=ct;
    ct++;
  }
  while(!p1.isEmpty()){
    Pair p=p1.poll();
    ans[p.ind]=ct;
    ct++;
  }
  for (int i:ans) {
    System.out.print(i+" ");
  }
  System.out.println("");
  }
  
 public static void main(String[] args) {
  int t = sc.nextInt();
  // int t=1;
  outer: for (int tt = 0; tt < t; tt++) {
    solve();
  }

}
static boolean isSubSequence(String str1, String str2,
                                 int m, int n)
    {
        int j = 0;
    for (int i = 0; i < n && j < m; i++)
            if (str1.charAt(j) == str2.charAt(i))
                j++;
        return (j == m);
    }
static long log2(long n){
  return (long)((double)Math.log((double)n)/Math.log((double)2));
}
static boolean isPrime(int n)
    {
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
  
        if (n % 2 == 0 || n % 3 == 0)
            return false;
  
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
  
        return true;
    }
public static int[] LPS(String s){
  int[] lps=new int[s.length()];
  int i=0,j=1;
  while (j<s.length()) {
    if(s.charAt(i)==s.charAt(j)){
      lps[j]=i+1;
      i++;
      j++;
      continue;
    }else{
      if (i==0) {
        j++;
        continue;
      }
      i=lps[i-1];
      while(s.charAt(i)!=s.charAt(j) && i!=0) {
        i=lps[i-1];
      }
      if(s.charAt(i)==s.charAt(j)){
      lps[j]=i+1;
      i++;
      }
      j++;
    }
  }
  return lps;
}
static long getPairsCount(int n, double sum,int[] arr)
    {
        HashMap<Double, Integer> hm = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (!hm.containsKey((double)arr[i]))
                hm.put((double)arr[i], 0);
            hm.put((double)arr[i], hm.get((double)arr[i]) + 1);
        }
        long twice_count = 0;
        for (int i = 0; i < n; i++) {
            if (hm.get(sum - arr[i]) != null)
                twice_count += hm.get(sum - arr[i]);
            if (sum - (double)arr[i] == (double)arr[i])
                twice_count--;
        }
        return twice_count / 2l;
    }
static boolean[] sieveOfEratosthenes(int n)
    {
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;
 
        for (int p = 2; p * p <= n; p++)
        {
            if (prime[p] == true)
            {
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        prime[1]=false;
        return prime;
 }
static long power(long x, long y, long p)
  {
    long res = 1l; 
    x = x % p;
    if (x == 0)
      return 0;
    while (y > 0)
    {

      if ((y & 1) != 0)
        res = (res * x) % p;
      y>>=1;
      x = (x * x) % p;
    }
    return res;
  }

public static int log2(int N)
    {
        int result = (int)(Math.log(N) / Math.log(2));
  
        return result;
    }

////////////////////////////////////////////////////////////////////////////////////
////////////////////DO NOT READ AFTER THIS LINE //////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////
static long modFact(int n, 
                       int p) 
    { 
        if (n >= p) 
            return 0; 
      
        long result = 1l; 
        for (int i = 3; i <= n; i++) 
            result = (result * i) % p; 
      
        return result; 
    } 
      
static boolean isPalindrom(char[] arr, int i, int j) {
  boolean ok = true;
  while (i <= j) {
    if (arr[i] != arr[j]) {
      ok = false;
      break;
    }
    i++;
    j--;
  }
  return ok;
}

static int max(int a, int b) {
  return Math.max(a, b);
}

static int min(int a, int b) {
  return Math.min(a, b);
}

static long max(long a, long b) {
  return Math.max(a, b);
}

static long min(long a, long b) {
  return Math.min(a, b);
}

static int abs(int a) {
  return Math.abs(a);
}

static long abs(long a) {
  return Math.abs(a);
}

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

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

static int maxArr(int arr[]) {
  int maxi = Integer.MIN_VALUE;
  for (int x : arr)
    maxi = max(maxi, x);
  return maxi;
}

static int minArr(int arr[]) {
  int mini = Integer.MAX_VALUE;
  for (int x : arr)
    mini = min(mini, x);
  return mini;
}

static long maxArr(long arr[]) {
  long maxi = Long.MIN_VALUE;
  for (long x : arr)
    maxi = max(maxi, x);
  return maxi;
}

static long minArr(long arr[]) {
  long mini = Long.MAX_VALUE;
  for (long x : arr)
    mini = min(mini, x);
  return mini;
}
static int lcm(int a,int b){
  return (int)(((long)a*b)/(long)gcd(a,b));
}
static int gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

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

static void ruffleSort(int[] a) {
  int n = a.length;
  Random r = new Random();
  for (int i = 0; i < a.length; i++) {
    int oi = r.nextInt(n);
    int temp = a[i];
    a[i] = a[oi];
    a[oi] = temp;
  }
  Arrays.sort(a);
}

public static int binarySearch(int a[], int target) {
  int left = 0;
  int right = a.length - 1;
  int mid = (left + right) / 2;
  int i = 0;
  while (left <= right) {
    if (a[mid] <= target) {
      i = mid + 1;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
    mid = (left + right) / 2;
  }
  return i-1;
}


static class FastScanner {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  StringTokenizer st = new StringTokenizer("");

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

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

  int[] readArray(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = nextInt();
    return a;
  }

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

  int[][] read2dArray(int n, int m) {
    int arr[][] = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        arr[i][j] = nextInt();
      }
    }
    return arr;
  }

  ArrayList<Integer> readArrayList(int n) {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    for (int i = 0; i < n; i++) {
      int a = nextInt();
      arr.add(a);
    }
    return arr;
  }

  long nextLong() {
    return Long.parseLong(next());
  }
}
 static class Pair {
  int val, ind;

  Pair(int fr, int sc) {
    this.val = fr;
    this.ind = sc;
  }
}
}