Jesse's Job#12930

Jesse's Job

2 seconds
256 megabytes
Medium

Jesse has a permutation p_1, p_2, \ldots, p_n of integers from to . His job is simple: to maximize the number of positions , for which p_i = i. To achieve that, Jesse can do the following operation exactly once:

For example, for permutation (3, 5, 1, 6, 2, 4), Jesse can mark numbers yellow, and blue. After sorting yellow and blue elements separately, Jesse will get permutation (3, 4, 1, 2, 6, 5).

Jesse's score in the end is the number of positions , for which p_i = i. Find the maximal score Jesse can achieve and some way to achieve it.

Input

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

The first line of each test case contains a single integer (2 \leq n \leq 10^6)  — the length of the permutation.

The second line of each test case contains integers p_1, p_2, \ldots, p_n (1 \le p_i \le n, all p_i are distinct)  — elements of the permutation.

It is guaranteed that the sum of over all test cases does not exceed 10^6.

Output

For every test case, in the first line, output the maximal score Jesse can achieve.

In the second line, output a single integer (1 \le k \le n-1)  — the number of elements Jesse should color yellow.

In the third line, output integers pos_1, pos_2, \ldots, pos_k (1 \le pos_i \le n, all pos_i are distinct)  — the positions of elements that you are going to color in yellow.

If there are several ways to obtain the maximum score, output any of them.

Examples

Example

Loading
Loading

Note

In the first test case, for permutation (p_1, p_2) = (2, 1), Jesse can mark p_1 yellow and p_2 blue. After sorting it will remain being , with score .

In the second test case, for permutation (p_1, p_2, p_3, p_4) = (2, 1, 4, 3), Jesse can mark p_1, p_2 yellow and p_3, p_4 blue. After sorting the permutation will become (1, 2, 3, 4), with score .