CF2219B1.Unique Values (Easy version)

The difference between the easy version and hard version is the maximum number of queries allowed. In this version, it is 66.

There is a secret array $ a $ of length $ 2n+1 $ , whose elements are integers from $ 1 $ to $ n $ . Each value appears exactly twice, except for one value, which appears exactly three times.

Your goal is to find the three positions of the value that appears three times.

To do this, you may ask the following query at most 66 times:

1. Choose an integer $ k $ and an array $ s $ of $ k $ distinct indices between $ 1 $ and $ 2n+1 $ .
2. You will receive the number of different values among $ a_{s_1}, a_{s_2}, \ldots, a_{s_k} $ that appear exactly once, or, in other words, the count of values that are not repeated.

For example, if the values $ a_{s_1}, \ldots, a_{s_k} $ are $ {2, 1, 2, 3, 2, 3, 6, 7} $ , the answer to the query will be 3, as 1, 6, 7 are the only values that appear exactly once. 3 appears 2 times and 2 appears 3 times, which is more than once, so they are not counted.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 1000 $ ).

The array $ a $ is fixed for the test case and does not change during the interaction. In other words, the interactor is not adaptive.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^4 $ .

null

The secret array is $ a = [1, 1, 1, 2, 2] $ .

In the first query, we ask for the number of values that appear exactly once in $ [a_1, a_2] = [1, 1] $ , since value 1 is repeated, the answer is 0.

In the second query, we ask for the number of values that appear exactly once in $ [a_1, a_4] = [1, 2] $ , since values 1 and 2 appear exactly once, the answer is 2.

In the fourth query, we ask for the number of values that appear exactly once in $ [a_1, a_2, a_3, a_4, a_5] = [1, 1, 1, 2, 2] $ , since values 1 and 2 are repeated, the answer is 0.

At the end, we print that the indices of the value repeated three times are 1, 2 and 3.