#P1605B. Reverse Sort
Reverse Sort
No submission language available for this problem.
Description
Ashish has a binary string of length that he wants to sort in non-decreasing order.
He can perform the following operation:
- Choose a subsequence of any length such that its elements are in non-increasing order. Formally, choose any such that and any sequence of indices such that .
- Reverse this subsequence in-place. Formally, swap with , swap with , and swap with (Here denotes the largest integer not exceeding , and denotes the smallest integer not less than )
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 operations.
The first line contains a single integer — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer — the length of the binary string .
The second line of each test case contains a binary string of length containing only s and s.
It is guaranteed that the sum of over all test cases does not exceed .
For each test case output the following:
- The minimum number of operations in the first line ().
- Each of the following lines should be of the form: ... , where is the length and are the indices of the chosen subsequence. For them the conditions from the statement must hold.
Input
The first line contains a single integer — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer — the length of the binary string .
The second line of each test case contains a binary string of length containing only s and s.
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each test case output the following:
- The minimum number of operations in the first line ().
- Each of the following lines should be of the form: ... , where is the length and are the indices of the chosen subsequence. For them the conditions from the statement must hold.
Samples
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:
- choose the indices
In the third test case, we can perform the following operation:
- choose the indices