CF2155D Batteries

This is an interactive problem. Refer to the Interaction section below for better understanding. There are $ n $ ( $ 2 \le n \le 40 $ ) batteries numbered $ 1, 2, \ldots, n $ . Some of them work while the others don't. Let $ a $ be the number of batteries that work. It is guaranteed that $ \mathbf{a \geq 2} $ . You are given $ n $ but not $ a $ . There is a flashlight which can hold two batteries and it only turns on when both batteries work. The batteries have been shuffled and you don't know which ones work and which ones don't. You can choose two batteries and try them in the flashlight. You want to find a pair of batteries that work. However, you are worried about breaking the flashlight, so you want to limit the amount of trials you attempt. Therefore, you should find a pair of working batteries using at most $ \left \lfloor \frac{n^2}{a} \right \rfloor $ trials. The interactor is adaptive. This means that whether battery $ i $ ( $ 1 \le i \le n $ ) works is not fixed and may change during the interaction. However, it is guaranteed that there exists a configuration of $ a $ working batteries that is consistent with the information that you have received so far.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 50 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 40 $ ) — the number of batteries. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 200 $ .

N/A

In the first test, there are $ 3 $ batteries. Only batteries $ 2 $ and $ 3 $ work. Therefore, $ a=2 $ and we have to find a pair of batteries that work in $ \lfloor \frac{n^2}{a} \rfloor = \lfloor \frac{3^2}{2} \rfloor = 4 $ queries. The interaction proceeds as follows: ParticipantJuryExplanation— $ 3 $ There are $ 3 $ batteries in this test case $ 1 $ $ 2 $ $ 0 $ The solution asks whether batteries $ 1 $ and $ 2 $ turn the flashlight on. The jury responds that they don't. $ 2 $ $ 3 $ $ 1 $ The solution asks whether batteries $ 2 $ and $ 3 $ turn the flashlight on. The jury responds that they do. A pair of batteries that work is found, so the interaction of the first test case terminates successfully.In the second test case, there are $ 10 $ batteries. Only batteries $ 1 $ , $ 4 $ , $ 6 $ and $ 9 $ work. Therefore, $ a=4 $ and we have to find a pair of batteries that work in $ \lfloor \frac{n^2}{a} \rfloor = \lfloor \frac{10^2}{4} \rfloor = 25 $ queries. The interaction proceeds as follows: ParticipantJuryExplanation— $ 10 $ There are $ 10 $ batteries in this test case. $ 1 $ $ 2 $ $ 0 $ The solution asks whether batteries $ 1 $ and $ 2 $ turn the flashlight on. The jury responds that they don't. $ 1 $ $ 3 $ $ 0 $ The solution asks whether batteries $ 1 $ and $ 3 $ turn the flashlight on. The jury responds that they don't. $ 1 $ $ 4 $ $ 1 $ The solution asks whether batteries $ 1 $ and $ 4 $ turn the flashlight on. The jury responds that they do. A pair of batteries that work is found, so the interaction of the first test case terminates successfully.Note that the line breaks in the example input and output are for the sake of clarity, and do not occur in the real interaction.