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.awt.image.BandedSampleModel;
import java.lang.reflect.Array;
import java.security.KeyPair;
import java.util.*;
import java.io.*;
import java.util.Map.Entry;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    public static class Matches implements Comparable<Matches>{
        public int quantity;
        public int amount;
        public Matches(Integer nameArg, Integer IPArg){
            quantity = nameArg;
            amount = IPArg;

        }

        @Override
        public String toString(){
            return quantity+" "+amount;
        }


        @Override
        public int compareTo(Matches o) {
            if(amount==o.amount)
                return 0;
            else if(amount<o.amount)
                return 1;
            else
                return -1;
        }

    }
    public static void main(String[] args) {
        // write your code here
        PrintWriter out = new PrintWriter(System.out);
        FastReader scan = new FastReader();
        Task solver = new Task();
        solver.solve(1,scan,out);
        out.close();


    }


    static class Task{

        public void solve(int testNumber, FastReader scan, PrintWriter out) {
            int [][] L = {{1,3,3,4,5,5,6},{2,2,4,1,1,4,2}};
            /*Pattern pattern = Pattern.compile("[B]+");  //REGEX template
            Matcher matcher = pattern.matcher(s);*/



            int t=1;
            t = scan.nextInt();


            for(int i=0; i<t;i++){
                int n = scan.nextInt();
                //long n = scan.nextLong();
                ArrayList<Integer> list = new ArrayList<>();
                ArrayList<Integer> list2 = new ArrayList<>();
                ArrayList<Integer> list3 = new ArrayList<>();
                HashMap<Integer, Integer> map = new HashMap<>();





                for(int j=0;j<n;j++){
                    int c = scan.nextInt();
                    list.add(c);
                    list2.add(c);
                }
                String s = scan.next();
                for(int j=0;j<n;j++){
                    map.put(list.get(j), Integer.parseInt(Character.toString(s.charAt(j))));
                }
                Set<Entry<Integer, Integer>> entries = map.entrySet();

                Comparator<Entry<Integer, Integer>> valueComparator = new Comparator<Entry<Integer,Integer>>() {
                    @Override public int compare(Entry<Integer, Integer> e1, Entry<Integer, Integer> e2)
                    {
                        Integer v1 = e1.getValue();
                        Integer v2 = e2.getValue();
                        Integer k1 = e1.getKey();
                        Integer k2 = e2.getKey();

                        if(v1.compareTo(v2)==0){
                            return -k1.compareTo(k2);
                        }
                        return -v1.compareTo(v2);
                    }
                };

                List<Entry<Integer, Integer>> listOfEntries
                        = new ArrayList<Entry<Integer, Integer>>(entries);


                Collections.sort(listOfEntries, valueComparator);
                for(int j=0;j<n;j++){
                    map.put(listOfEntries.get(j).getKey(), n-j);
                }
                for(int j=0;j<n;j++){
                    out.print(map.get(list.get(j))+" ");
                }
                out.println();















































               /* int min=0;
                int start =0;
                int maxEnd =0;
                for(int j=0;j<n;j++){
                    int c = scan.nextInt();
                    if(c==1){
                        min++;
                    }else{
                        int current =Math.min(-1, min-1);
                        if(min==-1){
                            start=j;
                            maxEnd=j;
                        }else{
                            maxEnd=j;
                        }
                    }
                }*/

































































































            }


        }
        public  boolean isLucky(int hh, int mm){
            if(hh%10==7 || mm%10==7){
                return true;
            }else{
                return false;
            }
        }

        public boolean isPalindrome(String s){
            boolean isOK=true;
            for(int j=0;j<s.length()/2;j++){
                if(s.charAt(j)!=s.charAt(s.length()-1-j)){
                    isOK=false;
                    break;
                }
            }
            return isOK;
        }

        public boolean isParenthesys(String s){
            boolean isOK=true;
            int number =0;
            for(int j=0;j<s.length();j++){
                if(s.charAt(j)=='('){
                    number++;
                }else{
                    number--;
                }
                if(number<0){
                    isOK=false;
                }
            }
            return isOK && number==0;
        }


        public static String parenthesys(int n){
            String answer = "";
            for(int j = 0; j<n;j++){
                answer+="(";
            }
            for(int j = 0; j<n;j++){
                answer+=")";
            }
            return answer;
        }
        public static long digitsSum(long n){
            long sum=0;
            while(n!=0){
                sum+=n%10;
                n=n/10;
            }
            return sum;
        }
        public static boolean isFibonachi(int n){
            int f1=1;
            int f2=1;
            while(f2<=n){
                if(f2==n){
                    return true;
                }
                int temp = f1+f2;
                f1=f2;
                f2=temp;
            }
            return false;
        }
        public static boolean isValid(int x, int y, int n){
            if(x<0 || y<0 || x>=n || y>=n){
                return false;
            }
            return true;
        }

        public static long factorial(long n){
            if(n<=1){
                return 1;
            }else{
                return n*factorial(n-1);
            }
        }

        public static long DBD(long a, long b){
            if (b==0) return a;
            return DBD(b,a%b);
        }
        public static boolean isPrime(int n){
            if(n<2){
                return false;
            }
            if(n==2){
                return true;
            }
            for(int i=2; i<Math.sqrt(n)+1 ;i++){
                if(n%i==0){
                    return false;
                }
            }
            return true;
        }
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

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

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        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;
        }
    }






}