human
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...
The above is tricky. Write me a correct solution in PYTHON3.

What is a Python program to find the one that has the smallest value of ∑_{i=1}^n |p_i-q_i|, where |x| is an absolute value of x?
assistant
#Here is Python program to find the one that has the smallest value of ∑_{i=1}^n |p_i-q_i|, where |x| is an absolute value of x.

import sys, collections, math, bisect, heapq, random, functools,io,os,copy
input = sys.stdin.readline
out = sys.stdout.flush
def rep():
    a = list(map(int,input().split()))
    return a

def sep():
    a = list(input().split())
    return a

class UnionFind:
    def __init__(self, x) -> None:
        self.uf = [-1] * x

    def find(self, x):
        r = x
        while self.uf[x] >= 0:
            x = self.uf[x]

        while r != x:
            self.uf[r], r = x, self.uf[r]
        return x

    def union(self, x, y):
        ux, uy = self.find(x), self.find(y)
        if ux == uy:
            return
        if self.uf[ux] >= self.uf[uy]:
            self.uf[uy] += self.uf[ux]
            self.uf[ux] = uy
        else:
            self.uf[ux] += self.uf[uy]
            self.uf[uy] = ux
        return

    def __print__(self):
        return self.uf

def spfa(x,g,n):
    dis = [float('inf') for i in range(n)]
    dis[x] = 0
    state = [False for i in range(n)]
    state[x] = True
    queue = collections.deque()
    queue.append(x)
    while queue:
        cur = queue.popleft()
        state[cur] = False
        for next_ in g[cur]:
            if dis[next_] > dis[cur] + 1:
                dis[next_] = dis[cur] + 1
                if state[next_] == False:
                    state[next_] = True
                    queue.append(next_)
    return dis

def gcd(x,y):
    if y == 0:
        return x
    return gcd(y,x % y)

def solve():
    n = int(input())
    a = rep()
    s = input().rstrip('\n')
    right,left = [],[]

    for i in range(n):
        if s[i] == '1':
            left.append([a[i],i])
        else:
            right.append([a[i],i])

    left.sort(key = lambda x:x[0])
    right.sort(key = lambda x:-x[0])
    m = {}
    cnt = len(right)
    l = cnt + 1
    for i in range(len(left)):
        cur,id = left[i]
        m[id] = l
        l += 1
    r = cnt
    for i in range(len(right)):
        cur,id = right[i]
        m[id] = r
        r -= 1
    ans = []
    for i in range(n):
       ...