Чёрная дыра

Учёные планируют провести измерение уровней излучения ряда чёрных дыр. Уровень излучения чёрной дыры задаётся целым числом от $1$ до $n$. Для измерения уровня излучения каждой чёрной дыры используется свой специальный орбитальный зонд, на котором установлен датчик излучения.

Датчик, установленный на зонде, может отвечать на следующие запросы: по значению $x$ определить, верно ли, что уровень излучения больше или равен $x$. К сожалению, из-за ошибки в программном обеспечении ответ датчика может быть неверным. К счастью, после первого же неверного ответа датчик этого зонда изменяет своё состояние и на все последующие запросы выдаёт только верные ответы.

Учёные хотят выяснить уровень излучения нескольких чёрных дыр, выполнив для каждой из них не слишком много запросов к датчику направленного к ней зонда.

Требуется написать программу, которая взаимодействует с программой жюри, симулирующей датчики зондов, и определяет уровень излучения каждой чёрной дыры.

Для каждого запуска программы-решения необходимо решить задачу для нескольких чёрных дыр с одинаковым значением $n$. Количество чёрных дыр в одном запуске не превосходит $100$ и не сообщается программе-решению. 

Для каждого теста жюри зафиксировано число $q$--- максимальное количество запросов, которые разрешается сделать для одной чёрной дыры. Гарантируется, что $q$ запросов достаточно, чтобы решить задачу независимо от того, какие ответы будет давать программа жюри. Это число не сообщается программе-решению. Ограничения $q$ в различных подзадачах приведены в таблице с информацией о системе оценки. Если программа-решение делает более $q$ запросов к программе жюри для одной чёрной дыры, то на этом тесте она получает в качестве результата тестирования <<Неверный ответ>>.

В первом примере для первой чёрной дыры после первых двух запросов неизвестно, на какой из них ответ датчика оказался неверным, поэтому необходим третий запрос. 

Во втором примере показан один из возможных вариантов взаимодействия для $n = 3$, который находит ответ за 5 запросов. Можно показать, что за 4 запроса узнать ответ нельзя. 

В обоих примерах решение проверяется со значением $q = 30$.

Обратите внимание, что программа жюри может давать другие ответы, даже если решение будет задавать ровно те же запросы, что в примере.