CF1605B.Reverse Sort

Ashish has a binary string $s$ of length $n$ that he wants to sort in non-decreasing order.

He can perform the following operation:

1. Choose a subsequence of any length such that its elements are in non-increasing order. Formally, choose any $k$ such that $1 \leq k \leq n$ and any sequence of $k$ indices $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$ such that $s_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_k}$.
2. Reverse this subsequence in-place. Formally, swap $s_{i_1}$ with $s_{i_k}$, swap $s_{i_2}$ with $s_{i_{k-1}}$, $\ldots$ and swap $s_{i_{\lfloor k/2 \rfloor}}$ with $s_{i_{\lceil k/2 \rceil + 1}}$ (Here $\lfloor x \rfloor$ denotes the largest integer not exceeding $x$, and $\lceil x \rceil$ denotes the smallest integer not less than $x$)

Find the minimum number of operations required to sort the string in non-decreasing order. It can be proven that it is always possible to sort the given binary string in at most $n$ operations.

阿什什有一个长度为 $n$ 的二进制字符串 $s$，他希望将其按非递减顺序排序。

他可以执行以下操作：

1. 选择一个任意长度的子序列，使得该子序列中的元素呈非递增顺序。形式化地，选择任意满足 $1 \leq k \leq n$ 的整数 $k$，以及任意满足 $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$ 的 $k$ 个下标，使得 $s_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_k}$。
2. 就地反转该子序列。形式化地，交换 $s_{i_1}$ 与 $s_{i_k}$，交换 $s_{i_2}$ 与 $s_{i_{k-1}}$，……，并交换 $s_{i_{\lfloor k/2 \rfloor}}$ 与 $s_{i_{\lceil k/2 \rceil + 1}}$（其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数，$\lceil x \rceil$ 表示不小于 $x$ 的最小整数）。

求将该字符串排序为非递减顺序所需的最少操作次数。可以证明：对任意给定的二进制字符串，总能在至多 $n$ 次操作内完成排序。

The first line contains a single integer $t$ $(1 \le t \le 1000)$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ $(1 \le n \le 1000)$ — the length of the binary string $s$.

The second line of each test case contains a binary string $s$ of length $n$ containing only $0$s and $1$s.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 1000$）—— 表示二进制字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$，其中仅包含字符 $0$ 和 $1$。

保证所有测试用例的 $n$ 值之和不超过 $1000$。

For each test case output the following:

• The minimum number of operations $m$ in the first line ($0 \le m \le n$).
• Each of the following $m$ lines should be of the form: $k$ $i_1$ $i_2$ ... $i_{k}$, where $k$ is the length and $i_1 \lt i_2 \lt ... \lt i_{k}$ are the indices of the chosen subsequence. For them the conditions from the statement must hold.

对每个测试用例，输出以下内容：

• 第一行输出操作的最小次数 $m$（$0 \le m \le n$）。
• 接下来的 $m$ 行中，每行格式为：$k$ $i_1$ $i_2$ ... $i_{k}$，其中 $k$ 为子序列长度，$i_1 \lt i_2 \lt ... \lt i_{k}$ 为所选子序列的下标。这些下标需满足题目陈述中的条件。

In the first test case, the binary string is already sorted in non-decreasing order.

In the second test case, we can perform the following operation:

• $k = 4:$ choose the indices ${1, 3, 4, 5}$

  $\underline{1}$ $0$ $\underline{1}$ $\underline{0}$ $\underline{0}$ $\rightarrow $ $\underline{0}$ $0$ $\underline{0}$ $\underline{1}$ $\underline{1}$

In the third test case, we can perform the following operation:

• $k = 3:$ choose the indices ${3, 5, 6}$

  $0$ $0$ $\underline{1}$ $0$ $\underline{0}$ $\underline{0}$ $\rightarrow $ $0$ $0$ $\underline{0}$ $0$ $\underline{0}$ $\underline{1}$

在第一个测试用例中，该二进制字符串本身已按非递减顺序排序。

在第二个测试用例中，我们可以执行以下操作：

• $k = 4:$ 选择下标 ${1, 3, 4, 5}$

  $\underline{1}$ $0$ $\underline{1}$ $\underline{0}$ $\underline{0}$ $\rightarrow $ $\underline{0}$ $0$ $\underline{0}$ $\underline{1}$ $\underline{1}$

在第三个测试用例中，我们可以执行以下操作：

• $k = 3:$ 选择下标 ${3, 5, 6}$

  $0$ $0$ $\underline{1}$ $0$ $\underline{0}$ $\underline{0}$ $\rightarrow $ $0$ $0$ $\underline{0}$ $0$ $\underline{0}$ $\underline{1}$