← Home
write a go solution for Description:
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<=k<=n and any sequence of k indices 1<=i_1lti_2ltldotslti_k<=n such that s_i_1>=s_i_2>=ldots>=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_lfloork/2rfloor with s_i_ceil(k/2)+1 (Here lfloorxrfloor denotes the largest integer not exceeding x, and ceil(x) 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.

Input Format:
The first line contains a single integer t (1<=t<=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<=n<=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 0s and 1s.

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

Output Format:
For each test case output the following:

- The minimum number of operations m in the first line (0<=m<=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_1lti_2lt...lti_k are the indices of the chosen subsequence. For them the conditions from the statement must hold.

Note:
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,5underline1 0 underline1 underline0 underline0 arrow underline0 0 underline0 underline1 underline1

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

- k=3: choose the indices 3,5,60 0 underline1 0 underline0 underline0 arrow 0 0 underline0 0 underline0 underline1. Output only the code with no comments, explanation, or additional text.