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.util.*;
import java.lang.*;
import java.nio.file.FileAlreadyExistsException;
import java.rmi.ConnectIOException;
import java.io.*;

public class Main {
    static FastReader in;
    static PrintWriter out;

    static int bit(long n) {
        return (n == 0) ? 0 : (1 + bit(n & (n - 1)));
    }

    static void p(Object o) {
        out.print(o);
    }

    static void pn(Object o) {
        out.println(o);
    }

    static void pni(Object o) {
        out.println(o);
        out.flush();
    }

    static String n() throws Exception {
        return in.next();
    }

    static String nln() throws Exception {
        return in.nextLine();
    }

    static int ni() throws Exception {
        return Integer.parseInt(in.next());
    }

    static long nl() throws Exception {
        return Long.parseLong(in.next());
    }

    static double nd() throws Exception {
        return Double.parseDouble(in.next());
    }

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

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

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

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

        String nextLine() throws Exception {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                throw new Exception(e.toString());
            }
            return str;
        }
    }

    static long power(long a, long b) {
        if (b == 0)
            return 1;
        long val = power(a, b / 2);
        val = val * val;
        if ((b % 2) != 0)
            val = val * a;
        return val;
    }

    static long power(long a, long b, long mod) {
        if (b == 0)
            return 1L;
        long val = power(a, b / 2) % mod;
        val = (val * val) % mod;
        if ((b % 2) != 0)
            val = (val * a) % mod;
        return val % mod;
    }

    static ArrayList<Long> prime_factors(long n) {
        ArrayList<Long> ans = new ArrayList<Long>();
        while (n % 2 == 0) {
            ans.add(2L);
            n /= 2L;
        }
        for (long i = 3; i <= Math.sqrt(n); i++) {
            while (n % i == 0) {
                ans.add(i);
                n /= i;
            }
        }
        if (n > 2) {
            ans.add(n);
        }
        return ans;
    }

    static void sort(ArrayList<Long> a) {
        Collections.sort(a);
    }

    static void reverse_sort(ArrayList<Long> a) {
        Collections.sort(a, Collections.reverseOrder());
    }

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

    static void swap(List<Long> a, int i, int j) {
        long temp = a.get(i);
        a.set(j, a.get(i));
        a.set(j, temp);
    }

    static void sieve(boolean[] prime) {
        int n = prime.length - 1;
        Arrays.fill(prime, true);
        for (int i = 2; i * i <= n; i++) {
            if (prime[i]) {
                for (int j = 2 * i; j <= n; j += i) {
                    prime[j] = false;
                }
            }
        }
    }

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

    static long mod = 1000000007;

    public static void sort(long[] arr, int l, int r) {
        if (l >= r)
            return;
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static void sort(int[] arr, int l, int r) {
        if (l >= r)
            return;
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    static void merge(int[] arr, int l, int mid, int r) {
        int[] left = new int[mid - l + 1];
        int[] right = new int[r - mid];
        for (int i = l; i <= mid; i++) {
            left[i - l] = arr[i];
        }
        for (int i = mid + 1; i <= r; i++) {
            right[i - (mid + 1)] = arr[i];
        }
        int left_start = 0;
        int right_start = 0;
        int left_length = mid - l + 1;
        int right_length = r - mid;
        int temp = l;
        while (left_start < left_length && right_start < right_length) {
            if (left[left_start] < right[right_start]) {
                arr[temp] = left[left_start++];
            } else {
                arr[temp] = right[right_start++];
            }
            temp++;
        }
        while (left_start < left_length) {
            arr[temp++] = left[left_start++];
        }
        while (right_start < right_length) {
            arr[temp++] = right[right_start++];
        }
    }

    static void merge(long[] arr, int l, int mid, int r) {
        long[] left = new long[mid - l + 1];
        long[] right = new long[r - mid];
        for (int i = l; i <= mid; i++) {
            left[i - l] = arr[i];
        }
        for (int i = mid + 1; i <= r; i++) {
            right[i - (mid + 1)] = arr[i];
        }
        int left_start = 0;
        int right_start = 0;
        int left_length = mid - l + 1;
        int right_length = r - mid;
        int temp = l;
        while (left_start < left_length && right_start < right_length) {
            if (left[left_start] < right[right_start]) {
                arr[temp] = left[left_start++];
            } else {
                arr[temp] = right[right_start++];
            }
            temp++;
        }
        while (left_start < left_length) {
            arr[temp++] = left[left_start++];
        }
        while (right_start < right_length) {
            arr[temp++] = right[right_start++];
        }
    }

    static class pair implements Comparable<pair> {
        int a, b, c;

        public pair(int a, int b,int c) {
            this.a = a;
            this.b = b;
            this.c=c;
        }

        public int compareTo(pair p) {
            return p.a - this.a;
        }

    }

    static HashMap<Long, Integer> map_prime_factors(long n) {
        HashMap<Long, Integer> map = new HashMap<>();
        while (n % 2 == 0) {
            map.put(2L, map.getOrDefault(2L, 0) + 1);
            n /= 2L;
        }
        for (long i = 3; i <= Math.sqrt(n); i++) {
            while (n % i == 0) {
                map.put(i, map.getOrDefault(i, 0) + 1);
                n /= i;
            }
        }
        if (n > 2) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        return map;
    }

    static int count = 1;
    static int[] p = new int[100002];
    static long[] flat_tree = new long[300002];
    static int[] in_time = new int[1000002];
    static int[] out_time = new int[1000002];
    static long[] subtree_gcd = new long[100002];
    static int w = 0;
    static boolean poss = true;

    static class comparator implements Comparator<pair> {
        public int compare(pair a, pair b) {
            if(a.a==b.a)return a.b-b.b;
            return b.a - a.a;
        }
    }

    public static void main(String[] args) throws Exception {
        in = new FastReader();
        out = new PrintWriter(System.out);
        int tc = ni();
        while (tc-- > 0) {
            int n=ni();
            int[] a=new int[n];
            TreeSet<pair> set=new TreeSet<>(new comparator());
            int count=0;
            for(int i=0;i<n;i++)
            {
                a[i]=ni();
            }
            String s=n();
            for(int i=0;i<n;i++)
            {
                if(s.charAt(i)=='1'){
                    set.add(new pair(1,a[i],i));
                    count++;
                }
                else set.add(new pair(0,a[i],i));
            }
            int j=0;
            int val=n-count+1;
            int[] ans=new int[n];
            while(!set.isEmpty()){
                pair p=set.pollFirst();
                ans[p.c]=val;
                j++;
                val++;
                if(j==count)val=1;
            }
            for(int i=0;i<n;i++){
                p(ans[i]+" ");
            }
            pn("");
            
        }

        out.flush();
        out.close();
    }

    static void swap(int a, int b) {
        pn("before" + a + " " + b);
        int temp = a;
        a = b;
        b = temp;
        pn("befor===e" + a + " " + b);
    }

    static void Union(int[] parent, int[] rank, int i, int j) {
        int x = find(i, parent);
        int y = find(j, parent);
        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else if (rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[x] = y;
            rank[y]++;
        }
    }

    static int find(int i, int[] parent) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i], parent);
    }

    static int area(Map<Integer, List<Integer>> map, int i, int j, boolean[][] visited, int max) {
        visited[i][j] = true;
        int total = 1;
        if (!map.containsKey(i * max + j))
            return total;
        for (int neighbour : map.get(i * max + j)) {
            int r = neighbour / max;
            int c = neighbour % max;
            if (!visited[r][c]) {
                total += area(map, r, c, visited, max);
            }
        }
        return total;
    }

    static void find(int l, int r, int level, int[] arr, int[] depth) {
        if (r < l)
            return;
        int max = find(l, r, arr);
        depth[max] = level;
        find(l, max - 1, level + 1, arr, depth);
        find(max + 1, r, level + 1, arr, depth);
    }

    static int find(int l, int r, int[] arr) {
        int index = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[index] < arr[i]) {
                index = i;
            }
        }
        return index;
    }

    static long start(int[] a, int k) {
        if (a.length == 0)
            return 0;
        if (a.length <= k)
            return 2 * a[a.length - 1];
        long ans = 0;
        int i = 0;
        for (i = k - 1; i < a.length; i += k) {
            ans += 2 * a[i];
        }
        i -= k;
        if (i != a.length - 1) {
            return ans + 2 * a[a.length - 1];
        } else
            return ans;
    }

    static long end(int[] a, int k) {
        if (a.length == 0)
            return 0;
        if (a.length <= k)
            return a[a.length - 1];
        if (k == 1) {
            long sum = 0;
            for (int i = 0; i < a.length - 1; i++)
                sum += 2 * a[i];
            return sum + a[a.length - 1];
        }
        long ans = 0;
        int i = 0;
        for (i = k - 1; i < a.length; i += k) {
            if (i != a.length - 1)
                ans += 2 * a[i];
        }
        i -= k;
        return ans + a[a.length - 1];
    }

    static void print(int[] a) {
        for (int i = 0; i < a.length; i++)
            p(a[i] + " ");
        pn("");
    }

    static long count(long n) {
        long count = 0;
        while (n != 0) {
            n /= 10;
            count++;
        }
        return count;
    }

    static void swap(long a, long b) {
        long temp = a;
        a = b;
        b = temp;
    }

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

    static int LcsOfPrefix(String a, String b) {
        int i = 0;
        int j = 0;
        int count = 0;
        while (i < a.length() && j < b.length()) {
            if (a.charAt(i) == b.charAt(j)) {
                j++;
                count++;
            }
            i++;
        }
        return a.length() + b.length() - 2 * count;
    }

    static void reverse(int[] a, int n) {
        for (int i = 0; i < n / 2; i++) {
            int temp = a[i];
            a[i] = a[n - i - 1];
            a[n - i - 1] = temp;
        }
    }

    static char get_char(int a) {
        return (char) (a + 'a');
    }

    static void dfs(int i, List<List<Integer>> arr, boolean[] visited, int parent) {
        visited[i] = true;
        for (int v : arr.get(i)) {
            if (!visited[v]) {
                dfs(v, arr, visited, i);
            }
        }
    }

    static int find1(List<Integer> a, int val) {
        int ans = -1;
        int l = 0;
        int r = a.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (a.get(mid) >= val) {
                r = mid - 1;
                ans = mid;
            } else
                l = mid + 1;
        }
        return ans;
    }

    static int find2(List<Integer> a, int val) {
        int l = 0;
        int r = a.size() - 1;
        int ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (a.get(mid) <= val) {
                ans = mid;
                l = mid + 1;
            } else
                r = mid - 1;
        }
        return ans;
    }

    static void dfs(List<List<Integer>> arr, int node, int parent, long[] val) {
        p[node] = parent;
        in_time[node] = count;
        flat_tree[count] = val[node];
        subtree_gcd[node] = val[node];
        count++;
        for (int adj : arr.get(node)) {
            if (adj == parent)
                continue;
            dfs(arr, adj, node, val);
            subtree_gcd[node] = gcd(subtree_gcd[adj], subtree_gcd[node]);
        }
        out_time[node] = count;
        flat_tree[count] = val[node];
        count++;
    }
}
