Problems
Вгадайте число
Вгадайте число
Це інтерактивна задача. Прочитайте умовну повністю, щоб зрозуміти, як працювати з такими задачами.
Журі загадало ціле число від $1$ до $n$, вам потрібно його вгадати. Ви можете запитувати будь-яке число від $1$ до $n$, а журі скаже <<1>>, якщо це число більше або рівне числу, яке загадало журі, або <<0>> інакше.
\InputFile
Перший рядок містить два цілі числа $t$ та $q$ ($1 \leq t \leq 100$)~--- кількість тестів та максимальна кількість запитів на кожен тест. Обмеження на $q$ нижче.
\Interaction
Для кожного набору вхідних даних спочатку слід зчитати ціле число $n$ ($1 \le n \le 1\,000$) --- максимально можливе загадане число.
Щоб зробити запит, виведіть <<1 $v$>> ($1 \le v \le n$).
У відповідь на запит програма журі виведе масив <<1>>, якщо $v$ більше або рівне за загадане число, інакше~--- <<0>>.
Після виведення запиту не забудьте вивести символ нового рядка і скинути буфер виведення. Для скидання буфера використовуйте:
\begin{itemize}
\item \t{fflush(stdout)} або \t{cout.flush()} в C++;
\item \t{System.out.flush()} в Java;
\item \t{flush(output)} в Pascal;
\item \t{stdout.flush()} в Python;
\end{itemize}
дивіться документацію для інших мов.
Зверніть увагу, що якщо ваш запит недійсний (ліміт запитів перевищено або вхідний масив не задовільняє обмеженням), інтерактор виведе <<-1>> та припинить роботу. Якщо ви зчитаєте <<-1>>, то негайно завершіть програму, щоб отримати вердикт \t{Неправильна відповідь} замість довільного вердикту.
Коли ви знатимете відповідь $a$, то виведіть <<2 $a$>>. Цей запит не враховується у ті $q$ запитів, які можна зробити.
Після цього, якщо це був останній набір вхідних даних, ви повинні завершити роботу своєї програми, в іншому випадку ви повинні продовжити роботу з наступним набором вхідних даних.
Для кожної з чотирьох мов (C++, Java, Python, Pascal) надано шаблон, який можна використовувати.
\Scoring
$q$ --- максимальна кількість запитів, яку може використати ваша програма.
\begin{enumerate}
\item ($40$ балів) $q=1\,000$;
\item ($59$ балів) $q=15$;
\item ($1$ бал) $q=10$.
\end{enumerate}
\Example
\begin{example}
\exmp{2 10
10
0
1
8
1
1
0}{
1 2
1 3
2 3
1 8
1 7
1 6
2 7
}
\end{example}