문제<\/h2>
There are $n<\/mi><\/mrow>n<\/math><\/span><\/span> n<\/span><\/span><\/span><\/span> houses with internet access in village J. In one of the houses, there lives a villain who is doing their villainous deeds: continuously writing us angry comments on social media from a fake account. We do not know which house they live in, but we want to find that out.<\/p> At the electrical substation, there are n<\/mi><\/mrow>n<\/math><\/span><\/span> n<\/span><\/span><\/span><\/span> switches, one for each house. When a switch is on, the light is on in the house, and when it is off, there is no light, and, by extension, no internet access. Initially, all switches are on. At the start of every hour, we can change the state of the switches in any way we wish: maybe turn some on and maybe turn some off. After that, for the next hour, we monitor social media: if the villain's house has light, comments will definitely appear, and if there is no light, there will be no comments. After our investigation, we must return everything to its original state: turn the light back on in all houses.<\/p> Unfortunately, if the light in the villain's house goes out more than k<\/mi><\/mrow>k<\/math><\/span><\/span> k<\/span><\/span><\/span><\/span> times, they will become suspicious, and we would like to avoid that. It is important to note that the light can safely be absent for a long time, it is the number of times we turn it off that counts. What is the minimum number of hours required for us to confidently determine which house the villain lives in and to restore the light in all houses?<\/p> 입력<\/h2> The first line contains an integer t<\/mi><\/mrow>t<\/math><\/span><\/span> t<\/span><\/span><\/span><\/span>: the number of test cases (1<\/mn>\leq<\/mo>t<\/mi>\leq<\/mo>2<\/mn>\cdot<\/mo>10<\/mn>5<\/mn><\/msup><\/mrow>1 \le t \leq 2 \cdot 10^5<\/math><\/span>$

Electrician