bool binary_search(int n, int p[], int target){
    int left = 1, right = n;
    while(left < right){
        int mid = (left + right) / 2;
        if(p[mid] == target)
            return true;
        else if(p[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    if(p[left] == target) return true;
    else return false;
}

众所周知，如果 $p$ 是有序的，那么当且仅当 target 出现在 $p$ 中时，该代码返回 true。然而，如果 $p$ 不是有序的，情况可能并非如此。

给定一个正整数 $n$ 和一个序列 $b_1, \dots, b_n \in \{\text{true}, \text{false}\}$。保证 $n = 2^k - 1$，其中 $k$ 为某个正整数。你需要生成一个 $\{1, \dots, n\}$ 的排列 $p$，使其满足特定条件。令 $S(p)$ 为满足 binary_search(n, p, i) 的返回值与 $b_i$ 不相等的下标 $i \in \{1, \dots, n\}$ 的个数。你需要设置 $p$ 使得 $S(p)$ 尽可能小（详见“数据范围”部分）。

（注：$\{1, \dots, n\}$ 的排列是一个包含 $1$ 到 $n$ 每个整数恰好一次的序列。）

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。接下来是各个测试用例。

每个测试用例的第一行包含整数 $n$。第二行包含一个长度为 $n$ 的字符串，仅由字符 '0' 和 '1' 组成。这些字符之间没有空格。如果第 $i$ 个字符是 '1'，则 $b_i = \text{true}$；如果第 $i$ 个字符是 '0'，则 $b_i = \text{false}$。

输出格式

输出数据包含每个测试用例的答案。每个测试用例的答案即为该测试用例生成的排列 $p$。

数据范围

• 令 $\sum n$ 为单个输入中所有 $n$ 的总和。
• $1 \le \sum n \le 100\,000$。
• $1 \le T \le 7\,000$。
• $n = 2^k - 1$，其中 $k \in \mathbb{N}, k > 0$。
• 如果对于子任务中的所有测试用例都有 $S(p) \le 1$，则该子任务得 100% 的分数。
• 否则，如果对于子任务中的所有测试用例都有 $0 \le S(p) \le \log_2 n$（即 $1 \le 2^{S(p)} \le n + 1$），则该子任务得 50% 的分数。

样例

输入 1

4
3
111
7
1111111
3
000
7
000000000

输出 1

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

输入 2

2
3
010
7
0010110

输出 2

3 2 1
7 3 1 5 2 4 6

说明

样例 1：前两个测试用例中，$S(p) = 0$。 在第三个测试用例中，$S(p) = 1$。这是因为 binary_search(n, p, 2) 返回 true，尽管 $b_2 = \text{false}$。 在第四个测试用例中，$S(p) = 1$。这是因为 binary_search(n, p, 4) 返回 true，尽管 $b_4 = \text{false}$。

样例 2：两个测试用例中均有 $S(p) = 0$。