Вгадайте число

Це інтерактивна задача. Прочитайте умовну повністю, щоб зрозуміти, як працювати з такими задачами.

Журі загадало ціле число від $1$ до $n$, вам потрібно його вгадати. Ви можете запитувати будь-яке число від $1$ до $n$, а журі скаже «1», якщо це число більше або рівне числу, яке загадало журі, або «0» інакше.

Вхідні дані

Перший рядок містить два цілі числа $t$ та $q$ ($1\le t\le 100$) — кількість тестів та максимальна кількість запитів на кожен тест. Обмеження на $q$ нижче.

Протокол взаємодії

Для кожного набору вхідних даних спочатку слід зчитати ціле число $n$ ($1\le n\le 1000$) — максимально можливе загадане число.

Щоб зробити запит, виведіть «1 $v$» ($1\le v\le n$).

У відповідь на запит програма журі виведе масив «1», якщо $v$ більше або рівне за загадане число, інакше — «0».

Після виведення запиту не забудьте вивести символ нового рядка і скинути буфер виведення. Для скидання буфера використовуйте:

• fflush(stdout) або cout.flush() в C++;

• System.out.flush() в Java;

• flush(output) в Pascal;

• stdout.flush() в Python;

дивіться документацію для інших мов.

Зверніть увагу, що якщо ваш запит недійсний (ліміт запитів перевищено або вхідний масив не задовільняє обмеженням), інтерактор виведе «-1» та припинить роботу. Якщо ви зчитаєте «-1», то негайно завершіть програму, щоб отримати вердикт Неправильна відповідь замість довільного вердикту.

Коли ви знатимете відповідь $a$, то виведіть «2 $a$». Цей запит не враховується у ті $q$ запитів, які можна зробити.

Після цього, якщо це був останній набір вхідних даних, ви повинні завершити роботу своєї програми, в іншому випадку ви повинні продовжити роботу з наступним набором вхідних даних.

Для кожної з чотирьох мов (C++, Java, Python, Pascal) надано шаблон, який можна використовувати.

Приклади

2 10
10

0

1

8

1

1

0

1 2

1 3

2 3

1 8

1 7

1 6

2 7

Оцінювання

$q$ — максимальна кількість запитів, яку може використати ваша програма.

1. ($40$ балів) $q=1000$;

2. ($59$ балів) $q=15$;

3. ($1$ бал) $q=10$.